研究の覚書

以下研究論文の覚書である．まずい訳もあるが見逃してほしいアル．．．

論文 A Survey of Two Verifiable Delay Function

3章より

∆(記号が見つからなかった)={(G,g,h,T):h=g^(2^T) in G}

に対するウェフロフスキーとピエトロザックの主張のセキュリティの分析

the row order assumption the adaptive root assumption に依存している．

独立ランダムな集合Sからxをランダムにとってくる．そしてA()はランダムアルゴリズムである．

もし|f(λ)|=o(1/λ^d) (d>0)なら整数の集合から実数の集合にする関数は無視できる．

ピエトロザックの主張のセキュリティ

GGen(λ)を群G(unknown order)を出力するランダムアルゴリズムとする．

low order assumption はGGen(λ)から出力された群のlow order element が見つけるのが難しいという仮定

low order assumption はGGen(λ)から出力された群Gを入力とし条件(μ^d=1,1≠μ in G,1<d<2^λ)で(μ,d)を出力する効率的なアルゴリズムAがないならこの仮定が成り立つ

利点は

LOadv(A,GGen(λ)):= Pr[μ^d=1,1≠μ in G,1<d<2^λ,:G←R GGen(λ),(μ,d)←R A(G)]

が無視できる確率である．

仮定が成り立つならピエトロザックの主張はsoundness error を無視できる．

errorの具体例はAを群Gを入力とし，条件(1<=T<2^t)のタプル(G,g,h,T) notin Δを間違って受理させることでその確率が無視できる確率であるといっている．

the low order assumption の必要性

the low order assumption はプロトコルの安全性に必要でないとセキュアじゃなくなる．

なぜなのかというとG←R GGen(λ),μ in G を known element order d > 1,(G,g,h,T) in Δ とすると 1/dの確立でタプル(G,g,hμ,T) notin Δ が間違って受理されることになる．

そうするにはproverがv ← g^(2^T/2)μ in Gを送り(G,g,μh,T)を間違って受理させる．このときverifierはrをr+1≡2^T/2(mod d)を満たすように選ぶ．この時dが大きいと確率1/dが無視できなくなる．

ウェフロフスキー主張のセキュリティ

下記の確立を満たす効率的な攻撃者(A_1,A_2)はいないとしている

ARadv(A_1,A_2),GGen(λ):=Pr[u^l=w≠1:G ←R GGen(λ),(w,state) ←R A_1(G),l ←R Primes(),u ←R A_2(l,state)]

この確率は常に少なくても1/|Primes(λ)|．Primes(λ)を大きな値で設定しなければならなく，それは攻撃者(A_1,A_2)が事前にlを正しく推測できてしまうとA_1がwとlからuを計算し，A_2はこのuを出力するためである．

adaptive root assumption の必要性

(A_1,A_2)を攻撃者とし，G ←R GGen(λ) プロトコルを攻撃するために任意のg in Gを選んでTを書き換え，条件w≠1で(w,state)←A_1(G)を通す．次にh←g^(2^T)をする．

verifierに(G,g,wh,T) notin Δ を間違って受理させる．verifierにl in Primes(λ)を出力させて

条件2^T=ql+r,0<=r<lでwh=π^lg^rとなるようなπを求める．そうするためにu^l=wとなるようなu in Gを得るA_2(l,state)を走らせる．

π:=ug^q(=w^(1/l)g^q)がproofになってverifierに送られる．

非対話型の確率変数のセキュリティ

非対話型の確率変数のセキュリティはfiat-shamir変換を使った非対話で作られた計算的に信頼性のあるrandom oracle modelのpublic-coin computationally sound protocolの示す一般的な論文に書いてある．