Develop with pleasure!

福岡でCloudとかBlockchainとか。

Schnorr + PQC署名のハイブリッドで強偽造不可能性を保持するBird of Prey

Cryptography Bitcoin

Pieter Wuilleが情報共有としてDelving Bitcoinで紹介していたハイブリッド署名スキームにおけるマリアビリティの回避に関する取り組みが興味深かった↓

Bird of Prey 2: non-malleable Schnorr + PQ signatures - Protocol Design - Delving Bitcoin

ここで言うハイブリッド署名スキームというのは、例えばSchnorr署名のような既存のデジタル署名スキームに加えて、PQCの署名スキームを合わせて使用するスキームのこと。量子コンピューター対策としてPQCのデジタル署名スキームを採用する際のネックは、その歴史の浅さから見落とされている脆弱性が存在する可能性があることで、そういった点を既存の署名スキームでカバーし、かつ量子耐性を持たせる。

このようなハイブリッド方式で最も素朴なのは、両方のスキームでそれぞれ署名し単純に連結する構成。この場合、どちらか一方が破られない限り、署名の偽造は不可能（EUF-CMA）であることは保証される。しかし強偽造不可能性（SUF-CMA）は保証されず、署名の一部（破られた方の署名）を別の署名に差し替えることができる。たとえばSchnorr署名の場合、秘密鍵を計算できた攻撃者は、別のnonceを選択することで、正当なユーザーが作成した署名とは異なる署名（R, s）を作ることができる（マリアブルな署名になる）。逆にPQCのデジタル署名スキームが古典的に破られた場合も同じ問題が起こる。

ハイブリッド方式において、署名のマリアビリティを排除するための提案が上記のスレッドで紹介されているBird of Prey。

Bird of Prey 2

EuroCrypt 2026の論文では、Bird of Preyのクラスとして3つ（BoP-1、BoP-2、BoP-3）提示していて、Delving Bitcoinのスレッドはそのうち2番目の構成を取り上げている。

  • BoP-1：BLSなどの一意な署名スキーム（メッセージと公開鍵に対して検証を通る署名が一意に定まるスキーム。この場合、偽造不可能性と強偽造不可能性は等価）
  • BoP-2：SchnorrやEdDSAのようなFiat-Shamir変換ベースの署名スキーム
  • BoP-3：RSA系

通常のBIP-340の署名スキームは、

  1. nonce kを選択し、
  2. R = kGを計算し公開nonceとし、
  3. e = H(R.x || P.x || m)を計算し（mは署名対象のメッセージ、Pは公開鍵）
  4. s = k + e * dを計算し（dはPの秘密鍵）
  5. (R.x, s)を署名とする。

という構成になっているけど、BoP-2ではチャレンジの作り方を変更することで、2つの署名をリンクする。具体的には、Schnorrの鍵ペアを {(d_{schnorr}, P_{schnorr})}、PQCスキームの鍵ペアを {(d_{pqc}, P_{pqc})}とした場合、署名の作成手順を以下のように変更する

  1. nonce kを選択し、
  2. R = kGを計算し
  3. e = H(R || P || m)を計算し（ここで {P = P_{schnorr} || P_{pqc}}）
  4. PQCの秘密鍵 {d_{pqc}}を使ってeに対してPQC署名 {\sigma_{pqc}}を生成する
  5. {s = k + H(\sigma_{pqc}) * d_{schnorr}}を計算し、
  6. {\sigma = (s, \sigma_{pqc})}を署名とする。

検証手順も以下のように変更する

  1. {R = s* G - H(\sigma_{pqc}) * P_{schnorr}}でRを復元し、
  2. e = H(R || P || m)を計算し
  3. {\sigma_{pqc}}を {P_{pqc}}とeに対して検証する

つまり、

  • PQCの署名は、メッセージそのものではなくSchnorrのチャレンジeに署名し、
  • Schnorr側のsは通常のチャレンジeの代わりに {H(\sigma_{pqc})}を係数として使用する

ことで両署名スキームをリンクする。この仕組みにより、片方の暗号を破って鍵を入手したとしても、そちら側の署名を差し替えることはできない。

  • sを変えると復元されるRが変わり、eが変わって {\sigma_{pqc}}が無効になり、
  • {\sigma_{pqc}}を変えると、 {H(\sigma_{pqc})}が変わってsが無効になる

という循環構造になる。

なお、この循環構造が機能するには、 {\sigma_{pqc}}がeを一意に固定していること、つまり「同じ {\sigma_{pqc}}が別のe値に対しても有効になる」ことがないという性質が必要で、しかもこの性質はPQCスキームが破られた後でも保たれる必要がある。PQC側が破られるケースでは攻撃者はPQCの秘密鍵を計算できる前提なので、そのスキームの困難性から来る性質はすべて失われる。もしこのとき複数のe値に対して同時に有効な {\sigma_{pqc}}を作れてしまうと、Schnorr側の鍵に触れることなく {\sigma_{pqc}}を差し替えられ、強偽造不可能性が破れる。ML-DSAなどでは、署名を固定したときにどのメッセージ（e）で検証が通るかはハッシュ関数のチェックで決まるため、格子仮定が崩壊してもこの性質は保たれる。

考慮事項

一方、以下のような考慮事項も挙げられている：

  • BoP-2スキームでは、sからRを復元するためSchnorr署名のバッチ検証ができなくなる。ただ、署名にRを含めなくてよくなるのでサイズ削減になる、PQCの署名の検証コストが支配的になるとSchnorrのバッチ検証を行うメリットは少ないという意見も。
  • Segwitの導入により署名のマリアビリティがTXIDに影響しなくなった状況で、このような特性は重要なのか？
    • Pieter Wuille自身も重要性は大きく低下しており、あると良いねレベルという評価。
  • そもそもハイブリッド化が必要か？
    • ハッシュベースであれば意義は薄く、格子ベースであれば賛成という意見が見られる。

⚡ Zap me!

Lightning QR

Lightning Address

techmedia_think@walletofsatoshi.com