Table of Contents

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

概要

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

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

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

定義

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

記法

集合 $S$ に対して $|S|$ は次数を表し、 $s \xleftarrow{\char36 } S$ で $S$ から $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$ を使って下から抑えられます。 $frk$ が $acc$ の二乗で表現できるのは、二回の $acc$ の試行を行うことから感覚的にも納得できると思います。

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

具体例

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

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

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

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

$p,q$ を素数とし、 $q$ は $p-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署名の存在的偽造に対する安全性も示していますが、条件分岐があるので証明はやや複雑です。