単一のSchnorr署名と同サイズの集約署名を可能にするDahLIAS

少し前に発表された集約署名の新しいスキームDahLIAS↓

eprint.iacr.org

自分も異なる文脈で集約署名という言葉を使ってるので紛らわしいけど、↑の集約署名というのは、MuSigやFROSTのように複数の署名者（公開鍵）が同じメッセージに署名するマルチシグの集約ではなく、複数の署名者（公開鍵）がそれぞれ異なるメッセージに対して署名した各署名を集約する署名スキームのこと。

このような集約が可能な署名スキームとしてはBLS署名が有名だけど、ペアリングを必要としない離散対数ベースの署名方式では、これまでSchnorr署名を用いた半集約が可能とされてきた↓

techmedia-think.hatenablog.com

半集約というのは、n人の署名者がそれぞれ異なるメッセージ ${m_i}$ に対するSchnorr署名 ${(R_i, s_i)}$ を提供した場合、それらのサイズは単純にn個分の ${(R_i, s_i)}$ （64×n byte）になるが、n個の ${R_i}$ と1つのs値、もしくは1つのR値とn個の ${s_i}$ 値に集約することで、署名データを約半分のサイズまで集約することができるというスキーム。

このような集約署名スキームには、

複数のインプットを持つトランザクションの複数の署名を集約する
ブロック内のトランザクションの署名を集約する
LNのチャネル通知をバッチ化する際に各通知の署名を集約する

といった用途がある。

今回提案されたDahLIASは、集約署名のサイズを単一のSchnorr署名のサイズまで圧縮する対話型のスキーム。対話型のスキームなので、上記の半集約のスキームのように後で非署名者が署名を集約するようなことはできない。つまり上記の1は可能だけど、2,3には対応できない。それでも単一のSchnorr署名と同じサイズにまで集約できるのは大きなメリットになる。

DahLIAS

DahLIASのスキームについて見ていく*1。n人の署名者と対話型のプロトコルを進めるコーディネーターがいるものとして、

各署名者の秘密鍵を ${x_i}$ とし、対応する公開鍵を ${P_i = x_iG}$ とする（Gは楕円曲線のベースポイント）
各署名者iが署名するメッセージを ${m_i}$ とする
${H_{non}, H_{sig}}$ を暗号額的ハッシュ関数とする*2

署名プロセスは、各署名者とコーディネーターの2ラウンドの通信で行われる以下の4つ（Sign, Coord, Sign', Coord'）のプロトコルで構成される。

Sign

最初の署名ラウンド（Sign）で、各署名者iは署名に使用するナンスにコミットする。

2つのシークレットナンス ${r_{1, i}, r_{2, i}}$ をランダムに選択し、
対応する公開ナンス ${R_{1, i} = r_{1, i}G, R_{2, i} = r_{2, i}G}$ を計算し、
第1ラウンドのステートとして ${st_{i} = (r_{1, i}, r_{2, i}, R_{2, i})}$ を保存し、
${out_i = (R_{1, i}, R_{2, i})}$ とし、コーディネーターに送信する。

ここでは公開ナンスを送るだけで、署名対象のメッセージにはコミットしてないので、事前処理が可能。

Coord

コーディネーターは、すべての署名者から公開鍵 ${P_i}$ およびメッセージ ${m_i}$ および最初のラウンドの ${out_i}$ を受け取ったら、

${R_1 = \sum_{i=1}^n R_{1, i}}$ と ${R_2 = \sum_{i=1}^n R_{2, i}}$ を計算し、
セッションコンテキスト ${ctx = (R_1, R_2, ( (P_1, m_1, R_{2, 1}), ..., (P_n, m_n, R_{2, n}) ))}$ を定義し*3、
${b = H_{non}(ctx)}$ を計算し、
${R = R_1 + bR_2}$ を計算し、
ステートst = Rを保存し、ctxを全署名者に送信する。

Sign'

2回めの署名ラウンド（Sign'）で、各署名者iは部分署名を作成する。

コーディネーターから受け取った ${ctx = (R_1, R_2, ((P_1, m_1, R_{2, 1}), ..., (P_n, m_n, R_{2, n})))}$ をパースし、
第1ラウンドで生成した ${R_{2, i}}$ と合致する ${R_{2, j}}$ が1つだけ存在するかチェックする。存在しない場合、一意ではない場合はプロセスを中止。
2をパスしたらそのインデックスをjとして、 ${(P_j, m_j) = (P_i, m_i)}$ かどうかチェックする。そうでない場合はプロセスを中止。
3をパスしたら、ctxの公開鍵とメッセージのペアから ${L = ( (P_1, m_1), ..., (P_n, m_n) )}$ を定義し、
${b = H_{non}(ctx)}$ を計算し、
${R = R_1 + bR_2}$ を計算し、
${c_i = H_{sig}(L, R, P_i, m_i)}$ を計算し、
部分署名 ${s_i = r_{1, i} + br_{2, i} + c_ix_i}$ を計算し、コーディネーターに送信する。

Coord'

${(s_1, ..., s_n)}$ を受け取ったコーディネーターは、 ${s = \sum_{i=1}^n s_i}$ を計算し、 ${\sigma = (R, s)}$ を返す。

検証

公開鍵とメッセージのリスト ${L = ( (P_1, m_1), ..., (P_n, m_n) )}$ と署名 ${\sigma = (R, s)}$ を受け取った検証者は、

${sG = R + \sum_{i=1}^n H_{sig}(L, R, P_i, m_i)P_i}$

が成立するか検証する。有効な署名であれば、sGは、

${sG = \sum_{i=1}^n s_iG = \sum_{i=1}^n(r_{1, i} + b r_{2, i} + c_ix_i)G = R_1 + bR_2 + \sum_{i=1}^n c_iP_i = R + \sum_{i=1}^n c_iP_i}$

であるため、↑の式は成立する。

通常のSchnorr署名の検証と異なるのは、 ${c_iP_i}$ を署名者の数分合算する点で、この検証方式はBellare-Nevenのマルチシグ方式と似ている。

ROS攻撃

通常のSchnorr署名であればナンスは１つのみだけど、Signラウンドで各署名者はナンスを2つ用意している。これは、攻撃者が複数の署名セッションを使って、正直な署名者のSignラウンドの出力 ${out_i}$ を得た後で、署名に使われる最終的なナンスは同じだがチャレンジの値 ${c_i}$ が異なる2つの署名セッションを作ることで、実際の署名者が署名していないメッセージに対する有効な署名を作成するという攻撃*4を回避するため。

具体的には、

${b = H_{non}(ctx)}$ と ${R = R_1 + bR_2}$ により、最終的なナンスがセッションコンテキストに依存することになる
Sign'ラウンドで ${R_{2, i}}$ と合致する ${R_{2, j}}$ の一意に存在するかのチェックと、同じインデックスで ${(P_j, m_j) = (P_i, m_i)}$ が成立するかのチェック

がこの回避策になってるみたい。

以上がDahLIASのスキーム。他にもTaprootで使用する際に必要になる鍵の調整に関する説明も論文には記載されてる。あと少しだけ触れられていたアトミックスワップへの適用とか面白そう。

*1:論文では離散対数ベースの乗法的表記になってるけど、この記事内では楕円曲線ベースの加法的表記で記載している

*2:タグ付きハッシュ関数とかでいいと思われる

*3:リストの順序を規定する必要がある。公開鍵とメッセージの辞書順とか

*4:https://eprint.iacr.org/2018/417.pdf

Develop with pleasure!

福岡でCloudとかBlockchainとか。