分岐補題(Forking Lemma)の解説と具体例

目次
  1. 概要
  2. 定義
    1. 記法
    2. 一般分岐補題(General Forking Lemma)
      1. Aの受理確率acc
      2. 分岐アルゴリズム
      3. 分岐アルゴリズムが1を返す確率frk
      4. 一般分岐補題の不等式
  3. 証明
  4. 解説
  5. 具体例
    1. シュノア署名の場合の証明
    2. まとめ
    3. 参考文献

概要

分岐補題(Forking Lemma)とは、ランダムオラクルモデル(ROM)を採用する署名形式の存在的偽造(=署名検証をパスする署名とメッセージの組を秘密鍵を知らないまま作り出す偽造)の難しさが、根底にある難しいと思われている問題(因数分解、離散対数問題など)の難しさと関連していることを保証するために使われる定理です。

「偽造が難しいこと」を示すために、「もし偽造ができたとすると、もっと難しい問題を解くことも(無視できない確率で)可能になる」という論理を頭に入れておくと読みやすいと思います。

ビットコインで様々なマルチシグの応用が提案されていますが、その応用の安全性の証明で分岐補題は用いられています[1]。この記事では証明を簡単に解説し、定理の意味するところを説明します。さらに、具体的にシュノア署名でこの定理がどう適用されているのか確かめてみたいと思います。

定義

以下の定義は[2]からの翻訳です。

記法

集合Sに対して|S|は次数を表し、s \xleftarrow{\char36 } SSからsへのランダムな要素の割り当てを表現する。Aがランダムな操作を含むアルゴリズムであるとき、A(x_{1},x_{2},...;\rho)はアルゴリズム内におけるランダムな操作のエンコーディング全体\rhoと入力x_{1}, x_{2}, ...によるアルゴリズムの出力とする。

y \xleftarrow{\char36 }A(x_{1}, x_{2}, ...)と書くとき

\rhoはランダムに選ばれるものとして、y = A(x_{1}, x_{2}, ...; \rho)とする。

一般分岐補題(General Forking Lemma)

以下ではxを公開鍵のようなパブリックパラメーターとし、h_{1}, h_{2}, ... , h_{q}をランダムオラクルから得られる値とする。

整数 q \geq 1(ランダムオラクルへのクエリの回数、偽造の試行回数)とh = |H| \geq 2 を集合 Hの要素数として与える。

ランダムアルゴリズムAは、x, h_{1}, ..., h_{q}を入力として受け取り、整数のペアを出力する。出力ペアの最初の要素は0 ... q のいずれかの整数であり、二番目の要素は署名\sigmaである。別のランダムアルゴリズムIGを入力生成器とする。

Aの受理確率acc

Aの受理確率accとは、以下の設定x, h_{1},...,h_{q}, (J,\sigma)J\geq 1となる確率である。

x \xleftarrow{\char36 } IG

h_{1}, h_{2}, ... , h_{q} \xleftarrow{\char36 } H

(J, \sigma) \xleftarrow{\char36 } A(x,h_{1},..., h_{q})

分岐アルゴリズム

A の分岐アルゴリズム F_{A}とは入力xを受け取るランダムアルゴリズムであって、以下のような操作を行うものである。

Algorithm \ \ F_{A}(x)

\rhoをランダムに選択する。

h_{1}, h_{2}, ... , h_{q} \xleftarrow{\char36 } H

(I, \sigma) \leftarrow A(x,h_{1},..., h_{q} ; \rho)

I=0ならば(0,\epsilon, \epsilon)を出力。

h_{I}^{\prime}, ... , h_{q}^{\prime} \xleftarrow{\char36 } H

(I^{\prime}, \sigma^{\prime}) \leftarrow A(x,h_{1},...,h_{I-1},h_{I}^{\prime},..., h_{q}^{\prime} ; \rho)

もしI^{\prime}=Iかつ h_{I} \neq h_{I}^{\prime} ならば(1,\sigma, \sigma^{\prime})を出力。

それ以外は(0,\epsilon, \epsilon)を出力.

分岐アルゴリズムが1を返す確率frk

分岐アルゴリズム F_{A}で出力の第一項が1になる確率frkは以下で定義される。

frk = Pr[b=1 : x \xleftarrow{\char36 } IG; (b,\sigma, \sigma^{\prime}) \xleftarrow{\char36 } F_{A}(x) ]

一般分岐補題の不等式

以下が成立する。

frk \geq acc \cdot (\frac{acc}{q} - \frac{1}{h})

または同じことであるが

acc \leq \frac{q}{h} + \sqrt{q\cdot frk}

証明

証明は[2]にあり、確率以外の特別な知識は必要としません。部分的に説明します。

以下の式変形を考えます。

Pr[I=I' \wedge I \geq 1]

= \sum^{q}_{i=1} Pr[I=i \wedge I'=i]

= \sum^{q}_{i=1} Pr[I=i]\cdot Pr[I'=i|I=i]

= \sum^{q}_{i=1} \sum^{}_{\rho, h_1,...,h_{i-1} } X_{i}^{2}(\rho,h_1,...,h_{i-1}) \cdot \frac{1}{|R|{|H|}^{i-1}}

= \sum^{q}_{i=1} E[X_{i}^{2}]

\geq \sum^{q}_{i=1} {E[X_{i}]}^{2}

Pr[I=i]\cdot Pr[I'=i|I=i](h_1,...,h_{i-1},\rho)という変数の全ての場合についてi-1番目までのパラメータをランダムに選んだとき、i番目以降のh_i,...,h_qが固定された場合のAの受理確率X_i(i\geq 1)を2回掛け合わせて足したものとして書きなおせます。ここでX_iは確率ですが、確率変数としてみる事もできます。確率変数としてみると、すなわち(h_1,...,h_{i-1},\rho)に関する自乗の期待値の和になっており、期待値の自乗の和で下から抑えられます。

解説

入力をパブリックパラメータx(公開鍵)とし、ハッシュ関数H_1を固定し、攻撃者が生成した公開ランダム値とメッセージを記録しながら、署名検証をパスする偽造署名を探索するアルゴリズムAを考えます。Aは攻撃者を模したアルゴリズムです。もしAによってメッセージハッシュ値H_1(m)、偽造署名\sigma、ランダム値\rhoが見つかったら、ランダム値を固定したまま、ハッシュ関数だけを別のH_2に取り替えて、同じような探索を行います(F_A(x))。すると、ハッシュ関数が一様にランダムであるため(ROM)一定の確率で1回目と同じメッセージについて存在的偽造に成功します。そのような連続した2回の存在的偽造に成功する確率frkは、そもそも存在的偽造が一回でも成功する確率accを使って下から抑えられます。frkaccの二乗で表現できるのは、二回のaccの試行を行うことから感覚的にも納得できると思います。

逆に言えば、accfrkで上から抑えられており、frkが「十分難しい問題を偶然解くことができる非常に小さな確率」とみなせるならば、accもまたいくらでも小さくできると言えます。このようにして、存在的偽造の困難性を示すために使われる定理ですが、実際の例を考えた方が理解しやすいでしょう。

具体例

[3]にあるシュノア署名[4]の例を挙げます。

frkとは、シュノア署名があるメッセージmに対して存在的偽造されたとき、その偽造で用いられたパラメータrを使ってもう一つmに対する有効な署名を作り出せる確率です。そして、そのような偽造が達成されたとき、離散対数問題は破られることを説明します。

シュノア署名の場合の証明

同じランダム値を使って存在的偽造された二つのシュノア署名が離散対数問題の解を導出することを示します。シュノア署名の詳細は[4]を参照してください。

p,qを素数とし、qp-1を割り切るとする。pを法としqを位数とする乗法群\mathbb{Z}_p^{*}を考える。q\mathbb{Z}_p^{*}の生成元gを割り切るように取る。\mathbb{Z}_p^{*}上のシュノア署名の検証をパスする、偽造された二つの署名を考える。

R = g^rを二つの偽造署名で共通のランダムな値とする(gは生成元なのでrは存在するが具体的には不明)。秘密鍵をx、公開鍵をyとする。

共通のR = g^rで偽造された2つのシュノア署名(e_1, t_1) , (e_2, t_2)について、以下が成立する。

e_1 = H_1(m; g^{t_1} y^{e1}) \neq e_2 = H_2(m; g^{t_2} y^{e2})

g^{t_1} y^{e_1} = R = g^{t_2}y^{e_2}\ mod\ p

よって

g^{t_2 - t_1} = y^{e_1 - e_2}\ mod\ p

ここでg^x = y\ mod\ pという形式の離散対数問題の解を求めてみる。

t = t_2 - t_1,\ e = e_1 - e_2 と置いて

g^t = y^e = g^{ex} \ mod \ p

位数qよりex=t\ mod\ q

x = (e_1-e_2)^{-1}(t_2 - t_1)\ mod\ q \ (e\neq 0)

が成立し、確かに「二つの存在的偽造署名」と「公開鍵」から「秘密鍵」が導出できているので、離散対数問題の解が得られていると言える。■

以下、上のシュノア署名の位数qとは異なる分岐補題の式のqであることに注意してください。

hを十分大きくとり(=大きなハッシュ空間を使い)、さらに\sqrt{q\cdot frk}が十分小さくなるようにfrkを十分小さく取れば(=シュノア署名の位数を十分大きく取れば)、離散対数問題の仮定のもと、ランダムに署名が偽造される確率accをいくらでも小さくなるように設定できます。よってシュノア署名はROMと離散対数問題の困難性の仮定の下で、存在的偽造に対して安全と言えることになります。

他にも[3]ではElGamal署名の存在的偽造に対する安全性も示していますが、条件分岐があるので証明はやや複雑です。

まとめ

英語でも情報が少なく、終始抽象的でイメージが掴みにくい分岐補題ですが、分かってしまえば言っていることは単純です。この定理の応用に興味があれば、他の署名形式での適用例を探してみたり自分で証明してみたりすると良いと思います。

参考文献

[1] https://eprint.iacr.org/2018/068.pdf

[2] http://cseweb.ucsd.edu/~mihir/papers/multisignatures-ccs.pdf

[3] https://www.di.ens.fr/david.pointcheval/Documents/Papers/2000_joc.pdf

[4] https://blog.visvirial.com/articles/721

コメントしてBTCを貰おう