分岐補題(Forking Lemma)の解説と具体例
概要
分岐補題(Forking Lemma)とは、ランダムオラクルモデル(ROM)を採用する署名形式の存在的偽造(=署名検証をパスする署名とメッセージの組を秘密鍵を知らないまま作り出す偽造)の難しさが、根底にある難しいと思われている問題(因数分解、離散対数問題など)の難しさと関連していることを保証するために使われる定理です。
「偽造が難しいこと」を示すために、「もし偽造ができたとすると、もっと難しい問題を解くことも(無視できない確率で)可能になる」という論理を頭に入れておくと読みやすいと思います。
ビットコインで様々なマルチシグの応用が提案されていますが、その応用の安全性の証明で分岐補題は用いられています[1]。この記事では証明を簡単に解説し、定理の意味するところを説明します。さらに、具体的にシュノア署名でこの定理がどう適用されているのか確かめてみたいと思います。
定義
以下の定義は[2]からの翻訳です。
記法
集合S
に対して∣S∣
は次数を表し、s$S
でS
からs
へのランダムな要素の割り当てを表現する。A
がランダムな操作を含むアルゴリズムであるとき、A(x1,x2,...;ρ)
はアルゴリズム内におけるランダムな操作のエンコーディング全体ρ
と入力x1,x2,...
によるアルゴリズムの出力とする。
y$A(x1,x2,...)
と書くとき
ρ
はランダムに選ばれるものとして、y=A(x1,x2,...;ρ)
とする。
一般分岐補題(General Forking Lemma)
以下ではx
を公開鍵のようなパブリックパラメーターとし、h1,h2,...,hq
をランダムオラクルから得られる値とする。
整数 q≥1
(ランダムオラクルへのクエリの回数、偽造の試行回数)とh=∣H∣≥2
を集合 H
の要素数として与える。
ランダムアルゴリズムA
は、x,h1,...,hq
を入力として受け取り、整数のペアを出力する。出力ペアの最初の要素は0...q
のいずれかの整数であり、二番目の要素は署名σ
である。別のランダムアルゴリズムIG
を入力生成器とする。
Aの受理確率acc
A
の受理確率acc
とは、以下の設定x,h1,...,hq,(J,σ)
でJ≥1
となる確率である。
x$IG
h1,h2,...,hq$H
(J,σ)$A(x,h1,...,hq)
分岐アルゴリズム
A
の分岐アルゴリズム FA
とは入力x
を受け取るランダムアルゴリズムであって、以下のような操作を行うものである。
Algorithm FA(x)
:
ρ
をランダムに選択する。
h1,h2,...,hq$H
(I,σ)←A(x,h1,...,hq;ρ)
I=0
ならば(0,ϵ,ϵ)
を出力。
hI′,...,hq′$H
(I′,σ′)←A(x,h1,...,hI−1,hI′,...,hq′;ρ)
もしI′=I
かつhI=hI′
ならば(1,σ,σ′)
を出力。
それ以外は(0,ϵ,ϵ)
を出力.
分岐アルゴリズムが1を返す確率frk
分岐アルゴリズム FA
で出力の第一項が1になる確率frk
は以下で定義される。
frk=Pr[b=1:x$IG;(b,σ,σ′)$FA(x)]
一般分岐補題の不等式
以下が成立する。
frk≥acc⋅(qacc−h1)
または同じことであるが
acc≤hq+q⋅frk
証明
証明は[2]にあり、確率以外の特別な知識は必要としません。部分的に説明します。
以下の式変形を考えます。
Pr[I=I′∧I≥1]
=∑i=1qPr[I=i∧I′=i]
=∑i=1qPr[I=i]⋅Pr[I′=i∣I=i]
=∑i=1q∑ρ,h1,...,hi−1Xi2(ρ,h1,...,hi−1)⋅∣R∣∣H∣i−11
=∑i=1qE[Xi2]
≥∑i=1qE[Xi]2
Pr[I=i]⋅Pr[I′=i∣I=i]
は(h1,...,hi−1,ρ)
という変数の全ての場合についてi−1
番目までのパラメータをランダムに選んだとき、i
番目以降のhi,...,hq
が固定された場合のAの受理確率Xi(i≥1)
を2回掛け合わせて足したものとして書きなおせます。ここでXi
は確率ですが、確率変数としてみる事もできます。確率変数としてみると、すなわち(h1,...,hi−1,ρ)
に関する自乗の期待値の和になっており、期待値の自乗の和で下から抑えられます。
解説
入力をパブリックパラメータx
(公開鍵)とし、ハッシュ関数H1
を固定し、攻撃者が生成した公開ランダム値とメッセージを記録しながら、署名検証をパスする偽造署名を探索するアルゴリズムA
を考えます。A
は攻撃者を模したアルゴリズムです。もしA
によってメッセージハッシュ値H1(m)
、偽造署名σ
、ランダム値ρ
が見つかったら、ランダム値を固定したまま、ハッシュ関数だけを別のH2
に取り替えて、同じような探索を行います(FA(x)
)。すると、ハッシュ関数が一様にランダムであるため(ROM)一定の確率で1回目と同じメッセージについて存在的偽造に成功します。そのような連続した2回の存在的偽造に成功する確率frk
は、そもそも存在的偽造が一回でも成功する確率acc
を使って下から抑えられます。frk
がacc
の二乗で表現できるのは、二回のacc
の試行を行うことから感覚的にも納得できると思います。
逆に言えば、acc
はfrk
で上から抑えられており、frk
が「十分難しい問題を偶然解くことができる非常に小さな確率」とみなせるならば、acc
もまたいくらでも小さくできると言えます。このようにして、存在的偽造の困難性を示すために使われる定理ですが、実際の例を考えた方が理解しやすいでしょう。
具体例
[3]にあるシュノア署名[4]の例を挙げます。
frk
とは、シュノア署名があるメッセージm
に対して存在的偽造されたとき、その偽造で用いられたパラメータr
を使ってもう一つm
に対する有効な署名を作り出せる確率です。そして、そのような偽造が達成されたとき、離散対数問題は破られることを説明します。
シュノア署名の場合の証明
同じランダム値を使って存在的偽造された二つのシュノア署名が離散対数問題の解を導出することを示します。シュノア署名の詳細は[4]を参照してください。
p,q
を素数とし、q
はp−1
を割り切るとする。p
を法としq
を位数とする乗法群Zp∗
を考える。q
はZp∗
の生成元g
を割り切るように取る。Zp∗
上のシュノア署名の検証をパスする、偽造された二つの署名を考える。
R=gr
を二つの偽造署名で共通のランダムな値とする(g
は生成元なのでr
は存在するが具体的には不明)。秘密鍵をx
、公開鍵をy
とする。
共通のR=gr
で偽造された2つのシュノア署名(e1,t1),(e2,t2)
について、以下が成立する。
e1=H1(m;gt1ye1)=e2=H2(m;gt2ye2)
gt1ye1=R=gt2ye2 mod p
よって
gt2−t1=ye1−e2 mod p
ここでgx=y mod p
という形式の離散対数問題の解を求めてみる。
t=t2−t1, e=e1−e2
と置いて
gt=ye=gex mod p
位数q
よりex=t mod q
x=(e1−e2)−1(t2−t1) mod q (e=0)
が成立し、確かに「二つの存在的偽造署名」と「公開鍵」から「秘密鍵」が導出できているので、離散対数問題の解が得られていると言える。■
以下、上のシュノア署名の位数q
とは異なる分岐補題の式のq
であることに注意してください。
h
を十分大きくとり(=大きなハッシュ空間を使い)、さらにq⋅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