Loading [MathJax]/extensions/tex2jax.js

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

お知らせ
Table of Contents

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

概要

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

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

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

定義

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

記法

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

一般分岐補題(General Forking Lemma)

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

整数 q1q \geq 1(ランダムオラクルへのクエリの回数、偽造の試行回数)とh=H2h = |H| \geq 2 を集合 HHの要素数として与える。
ランダムアルゴリズムAAは、x,h1,...,hqx, h_{1}, ..., h_{q}を入力として受け取り、整数のペアを出力する。出力ペアの最初の要素は0...q0 ... qのいずれかの整数であり、二番目の要素は署名σ\sigmaである。別のランダムアルゴリズムIGIGを入力生成器とする。

Aの受理確率acc

AAの受理確率accaccとは、以下の設定x,h1,...,hq,(J,σ)x, h_{1},...,h_{q}, (J,\sigma)J1J\geq 1となる確率である。

x$IGx \xleftarrow{\char36 } IG

h1,h2,...,hq$Hh_{1}, h_{2}, ... , h_{q} \xleftarrow{\char36 } H

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

分岐アルゴリズム

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

Algorithm  FA(x)Algorithm \ \ F_{A}(x)

  ρ\rhoをランダムに選択する。
  h1,h2,...,hq$Hh_{1}, h_{2}, ... , h_{q} \xleftarrow{\char36 } H
  (I,σ)A(x,h1,...,hq;ρ)(I, \sigma) \leftarrow A(x,h_{1},..., h_{q} ; \rho)
  I=0I=0ならば(0,ϵ,ϵ)(0,\epsilon, \epsilon)を出力。
  hI,...,hq$Hh_{I}^{\prime}, ... , h_{q}^{\prime} \xleftarrow{\char36 } H
  (I,σ)A(x,h1,...,hI1,hI,...,hq;ρ)(I^{\prime}, \sigma^{\prime}) \leftarrow A(x,h_{1},...,h_{I-1},h_{I}^{\prime},..., h_{q}^{\prime} ; \rho)
  もしI=II^{\prime}=IかつhIhIh_{I} \neq h_{I}^{\prime}ならば(1,σ,σ)(1,\sigma, \sigma^{\prime})を出力。
  それ以外は(0,ϵ,ϵ)(0,\epsilon, \epsilon)を出力.

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

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

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

一般分岐補題の不等式

以下が成立する。

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

または同じことであるが

accqh+qfrkacc \leq \frac{q}{h} + \sqrt{q\cdot frk}

証明

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

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

Pr[I=II1]Pr[I=I' \wedge I \geq 1]
=i=1qPr[I=iI=i]= \sum^{q}_{i=1} Pr[I=i \wedge I'=i]
=i=1qPr[I=i]Pr[I=iI=i]= \sum^{q}_{i=1} Pr[I=i]\cdot Pr[I'=i|I=i]
=i=1qρ,h1,...,hi1Xi2(ρ,h1,...,hi1)1RHi1= \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}}
=i=1qE[Xi2]= \sum^{q}_{i=1} E[X_{i}^{2}]
i=1qE[Xi]2\geq \sum^{q}_{i=1} {E[X_{i}]}^{2}

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

解説

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

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

具体例

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

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

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

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

p,qp,qを素数とし、qqp1p-1を割り切るとする。ppを法としqqを位数とする乗法群Zp\mathbb{Z}_p^{*}を考える。qqZp\mathbb{Z}_p^{*}の生成元ggを割り切るように取る。Zp\mathbb{Z}_p^{*}上のシュノア署名の検証をパスする、偽造された二つの署名を考える。
R=grR = g^rを二つの偽造署名で共通のランダムな値とする(ggは生成元なのでrrは存在するが具体的には不明)。秘密鍵をxx、公開鍵をyyとする。
共通のR=grR = g^rで偽造された2つのシュノア署名(e1,t1),(e2,t2)(e_1, t_1) , (e_2, t_2)について、以下が成立する。
e1=H1(m;gt1ye1)e2=H2(m;gt2ye2)e_1 = H_1(m; g^{t_1} y^{e1}) \neq e_2 = H_2(m; g^{t_2} y^{e2})
gt1ye1=R=gt2ye2 mod pg^{t_1} y^{e_1} = R = g^{t_2}y^{e_2}\ mod\ p
よって
gt2t1=ye1e2 mod pg^{t_2 - t_1} = y^{e_1 - e_2}\ mod\ p
ここでgx=y mod pg^x = y\ mod\ pという形式の離散対数問題の解を求めてみる。
t=t2t1, e=e1e2t = t_2 - t_1,\ e = e_1 - e_2 と置いて
gt=ye=gex mod pg^t = y^e = g^{ex} \ mod \ p
位数qqよりex=t mod qex=t\ mod\ q
x=(e1e2)1(t2t1) mod q (e0)x = (e_1-e_2)^{-1}(t_2 - t_1)\ mod\ q \ (e\neq 0)
が成立し、確かに「二つの存在的偽造署名」と「公開鍵」から「秘密鍵」が導出できているので、離散対数問題の解が得られていると言える。■

以下、上のシュノア署名の位数qqとは異なる分岐補題の式のqqであることに注意してください。
hhを十分大きくとり(=大きなハッシュ空間を使い)、さらにqfrk\sqrt{q\cdot frk}が十分小さくなるようにfrkfrkを十分小さく取れば(=シュノア署名の位数を十分大きく取れば)、離散対数問題の仮定のもと、ランダムに署名が偽造される確率accaccをいくらでも小さくなるように設定できます。よってシュノア署名は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

タイトルとURLをコピーしました