Develop with pleasure!

福岡でCloudとかBlockchainとか。

非対話型のSchnorr署名のハーフアグリゲーション

Cryptography Schnorr

先日、Blockstreamのブログ記事↓で、非対話型のSchnorrの署名集約スキームについて知ったので、

medium.com

↑にリンクされているドラフトBIPに記載されていた↓のペーパーを斜め読みしてみた。

https://eprint.iacr.org/2022/222.pdf

Schnorr署名の集約と言えば、Bitcoinの文脈だと、MuSig2などの対話型の集約プロトコルが有名で、このような集約方法をフルアグリゲーションと呼ぶみたい。これはマルチシグをSchnorr署名の集約特性を利用して実現する方式で、複数の参加者が共通のメッセージに対して対話的に署名を生成し、それを単一の署名に集約する。

↑のハーフアグリゲーションは、マルチシグのような対話型の署名方式ではなく、署名者同士はそれぞれ互いを知らずに個々の署名を生成し、その後不特定の集約者がその署名を集約することを想定している。マルチシグは対話型で、共通のチャレンジに対して署名を生成し、それが単一のSchnorr署名と見分けが付かないような集約アプローチになるのに対して、ハーフアグリゲーションでは各署名者が異なるメッセージにそれぞれ署名し、その署名のサイズが個々の署名データの合算値の約半分になるというもの（フルアグリゲーションのように単一のSchnorr署名と同じサイズになる訳ではない）。そして個々の有効なSchnorr署名をインクリメンタル/シーケンシャルに集約することができる。

この仕組みを活用すると、例えば、

といった事が可能になる。

ペーパーでは、3つのハーフアグリゲーション方式が説明されている（以下、表記は楕円曲線ベースのものに変えてる）。

ASchnorr

Chalkiasらによって提案された集約方式をASchnorrと呼んでいる。

公開鍵 {X_1, X_2}とメッセージ {m_1, m_2}に対するSchnorr署名を {\sigma_1 = (R_1, s_1), \sigma_2 = (R_2, s_2)}として、各チャレンジを {c_1 = H_1(R_1, m_1), c_2 = H_1(R_2, m_2)}とした場合、それぞれ有効なSchnorr署名であれば、以下が成立する。

  • {s_1G = R_1 + c_1X_1}
  • {s_2G = R_2 + c_2X_2}

この2つの署名を単純にハーフアグリゲーションしようとすると、 {\tilde{s} = s_1 + s_2}とする方法で、 {\tilde{s}G = R_1 + c_1X_1 + R_2 + c_2X_2}が成立するか検証する方法。

ただ、この集約方法は安全ではない。ある署名のチャレンジ（たとえば、 {c_1}）がもう１つの署名のコミットメント（ {R_2}）に依存していないため、例えば {R_2}を {R_2 = r_2G - (R_1 + c_1X_1)}と細工すれば、 {X_1}の離散対数の知識を必要とせずに、 {X_2}の離散対数の知識のみで集約署名を偽造することができる。

ASchnorrでは、各署名に以下のような外部係数を使用して、この偽造問題に対処している。

{L = \lbrace (R_1, X_1, m_1), (R_2, X_2, m_2) \rbrace}

および、

{a_1 = H_2(L, 1), a_2 = H_2(L, 2)}

として、集約署名を {\tilde{s} = a_1s_1 + a_2s_2}として、その署名の有効性の検証は、 {\tilde{s}G = a_1 \cdot (R_1 + c_1X_1) + a_2\cdot(R_2 + c_2X_2)}とするというもの。MuSigのアプローチと似てる。

IASchnorr

↑のASchnorrで集約は可能だが、インクリメンタルな集約サポートしていないので、個々の署名がすべて集まってから集約する必要がある。そこで、インクリメンタルな集約をサポートするハーフアグリゲーション方式がIASchnorrと呼ばれる方式。

↑の2つの署名が集約された後に、公開鍵 {X_3}とメッセージ {m_3}に対する署名 {\sigma_3 = (R_3, s_s)}が届いて、これを既存の集約署名に追加するケースを想定する。

単純に集約使用とすると、既に集約済みの署名を通常の署名として扱うことで再度ASchnorrを行うというもの。つまり、

{L' = \lbrace L, (R_3, X_3, m_3) \rbrace}

および、

{a'_1 = H_2(L', 1), a'_2 = H_2(L', 2)}

として、 {\tilde{s}' = a'_1 \tilde{s} + a'_2s_3}という集約をする方法。

ただ、この方法の問題は、3つの署名が同じタイミングで集約された場合と、↑のようにインクリメンタルに集約された場合とで、集約結果の署名値が異なり、正しく検証するために、それがどのように集約されたのかという情報が追加で必要になる。

IASchnorrでは、係数を個々の署名すべてから計算するのではなく、それ以前の署名にのみ依存させるよう生成することで、この問題に対処するようになっている。つまり

{L_i = \lbrace (R_1, X_1, m_1), ..., (R_i, X_i, m_i)\rbrace}

として、i番めの係数は {a_i = H_2(L_i)}となる。こうすると、↑のように署名集約のタイミングによって集約値が異なるようなケースを回避できる。

この方式では、n個の公開鍵とメッセージに対する最終的な署名値は、 {(\lbrace R_1, ..., R_n \rbrace, \tilde{s}'_n)}

SASchnorr

最後に、SASchnorrが、このペーパーで新しく提案されているハーフアグリゲーションの方式で、シーケンシャルに集約した個別の署名をリカバリーできるという特徴を持つ。また集約の方式もASchnorrやIASchnorrとは結構違う。

署名者nは、n-1個の公開鍵 {X_1, ..., X_{n-1}}とメッセージ {m_1, ..., m_{n-1}}に対する集約署名 {(\tilde{R}_{n-1}, \lbrace s_1, ..., s_{n-1} \rbrace)}を受け取ると、 {R_n = r_nG}の代わりに集約コミットメント {\tilde{R_n} = \tilde{R}_{n-1} + R_n}を計算し、チャレンジ {c_n = H(\tilde{R}_n, X_n, m_n, s_{n-1}, n)}を計算し、署名値 {s_n = r_n + c_n x_i}を計算する。

{(\tilde{R}_{n}, \lbrace s_1, ..., s_{n} \rbrace)}を受け取った検証者は、 {c_n}を計算すると、 {R_n = s_nG - c_nX_n}を計算することで、１つ前の {\tilde{R}_{n-1} = \tilde{R}_n - R_n}を復元することができる。これを繰り返すことで、検証者はすべての個々の署名を復元することができる。

ペーパーでは、ランダムオラクルモデルの下で、Schnorr署名と同等の安全性を証明している。

↑の方式見た感じだと、各署名値が前の署名値に依存しているので、署名フェーズがシーケンシャルになる必要が出てくる。

データサイズ

↑のようにn個の公開鍵とメッセージに対して、以下署名データが必要になる。

  • IASchnorrの場合、 {(\lbrace R_1, ..., R_n \rbrace, \tilde{s}'_n)}＝n個のRと1つのs
  • SASchnorrの場合、 {(\tilde{R}_{n}, \lbrace s_1, ..., s_{n} \rbrace)}＝1つのR値とn個のs値

個別のSchnorr署名だとn個のRとn個のsで構成されるため、約半分のデータサイズになっていることが分かる。だからハーフアグリゲーションというネーミングなのね。

ドラフトBIP

ドラフトBIPでは、インクリメンタルなハーフアグリゲーションをサポートするようなので、↑の2番めのアプローチがベースになってる模様。まぁ、ブロックやトランザクションの署名を集約するようなケースだと、SASchnorrのようなシーケンシャルな署名プロセスは採用できないので、インクリメンタルなアプローチになるよね。SASchnorrの方は証明書チェーンやルーティングプロトコルなでの利用が期待されているみたい。