2013/06/04 強一方向性関数 •  計算が容易： –  多項式時間アルゴリズム　が存在して，任意の A f ( x) 入力　に対して　は　を出力する． A x 暗号基盤特論 ハードコア関数 (M43160) •  逆計算が困難： B –  どんな確率的多項式時間アルゴリズム　を考えても，以下の値は無視できる． Pr[ B( f (U n ),1n ) ∈ f −1 ( f (U n ))] 5 June, 2013 小柴健史 1 2 一方向性，再考一方向性関数とハードコアビット f •  を一方向性関数とする •  以下で構成される関数を考える •  •  •  簡単 ! (多項式時間計算可能) 入力 x f !(xb) def = f (x)b は依然として一方向性関数 f ʹ′ f ʹ′ の逆像の最下位ビットは100%分かる出力 f (x ) 難しい ! (多項式時間では計算できない) とはいえ，すべてが分かるわけでは無いどこかに計算が難しい部分がある！ 3 Goldreich-Levin の定理ハードコア述語 •  計算が容易： f •  を一方向性関数とする •  以下で構成される関数を考える –  多項式時間アルゴリズム　が存在して，任意の A 入力　に対して　は　を出力する． A b( x ) x f !(x, r) def = ( f (x), r) x = x1 x2 xn , r = r1r2 rn •  予測が困難： –  どんな確率的多項式時間アルゴリズム　を考え B ても、以下の値は無視できる． Pr[ B( f (U n ),1n ) = b(U n )] − 4 1 2 f b は　のハードコア述語という！ 5 f ʹ′ •  は依然として一方向性関数このとき， n def b(x, r) = x, r = ∑ xi ri mod 2 i=1 は　のハードコア述語である f ʹ′ 6 1 2013/06/04 証明の方針証明の方針 –  対偶を示す．つまり，　がハードコア述語でない b とすると，　は一方向性関数でない，ことを示す f ʹ′ A •  厳密に言うと，以下を示す． –  ある確率的多項式時間アルゴリズム　とある多 B 項式　が存在し，無限に多くの　で p n f (x), r 1 1 Pr[B( f !(U n ,U n! )) = b(U n ,U n! )] > + 2 p(n) x, r B x!, r! f ( x!), r! –  このとき，ある確率的多項式時間アルゴリズム　A q n とある多項式　が存在し，無限に多くの　で Pr[A( f !(U n ,U n! )) ∈ f "−1 ( f "(U n ,U n! ))] > 1 q(n) 7 8 完全予測可能な場合証明の方針 Pr[B( f !(U n ,U n! )) = b(U n ,U n! )] = Pr[B( f (U n ),U n! ) = b(U n ,U n! )] = 1 A f ( x) •  から　を求めたい！ x –  について i = 1,..., n –  B( f (x),00100) = b(x,00100) = xi i 番目 i 番目 ei f (x), r x, r Bx x, r f (x), r –  は所望の　の逆像 f ( x) x x x 1 2 n 9 問題設定の微修正自己訂正 •  予測サブルーチンBx :{0,1} → {0,1} 1 ε Pr[ Bx (r ) = x, r : r ← {0,1}n ] = + 2 2 x •  目的は　を用いて　を求めること Bx •  B　の答えは常に同じかもしれない x ( z) n –  x, z = x, z ⊕ r ⊕ x, r # n & # n & x, z ⊕ r ⊕ x,r = %% ∑ xi (zi ⊕ ri ) mod 2 (( ⊕ %% ∑ xi ri mod 2 (( $ i=1 ' $ i=1 ' G = {s ∈{0,1} : Bx ( s) = x, s n B = {s ∈{0,1} : Bx ( s) ≠ n –  1+ ε G = 2 n ⋅2 , 10 } x, s } n = ∑ xi zi ⊕ xi ri ⊕ xi ri mod 2 i=1 n 1− ε n B= ⋅2 2 = ∑ xi zi mod 2 = x, z 11 i=1 Bx (r ) Bx ( z ) B　x ( z ⊕ r ) と　の答えが共に正しければ　の代替 12 2 2013/06/04 自己訂正自己訂正 •  アルゴリズムSCx ( z ) SCx ( z ) •  アルゴリズム　の評価 n r ← {0,1} b1 ← Bx ( z ⊕ r ) Pr #$b1 ⊕ b2 ≠ x, z %& ≤ Pr #$ Bx (z ⊕ r) ≠ x, z ⊕ r ∨ Bx (z) ≠ x, z %& = Pr #$ z ⊕ r ∈ B∨ r ∈ B%& ≤ Pr #$ z ⊕ r ∈ B%& + Pr #$r ∈ B%& ,1 ε / = 2⋅. − 1 -2 20 = 1− ε δ b2 ← Bx (r ) output b1 ⊕ b2 の失敗確率 SC x ( z) 13 14 自己訂正アルゴリズムの適用更なる改善 SCx (ei ) = 1,..., n •  i　について　の適用 •  SC の正解は　xi x (ei ) •  すべて正解となる確率は少なくとも1 − nδ •  δ ≤ 1 2n ならば正解確率は少なくとも 1/2 •  •  •  •  •  •  •  [k ] = {1,..., k} パラメータm = c log(n) R = (r1 , r2 ,..., rm ), ri ∈{0,1}n R[S] = ⊕ rj S ⊆ [ m] に対して　j∈S ：　のすべての部分集合 S1 ,..., S 2m [m] かもしれない値 b1 , b2 ,..., bm : b j = x, rj S ⊆ [ m] に対して b[S] = ⊕ b j j∈S 15 更なる改善自己訂正（強力版） x, z = x, z ⊕ R[Si ] ⊕ x, ⊕ x, z = x, z ⊕ R[Si ] ⊕ ⊕ 16 j∈Si j∈Si •  アルゴリズムSSCx ( z; r1 ,..., rm ; b1 ,..., bm ) rj s←0 For i ← 1,..., 2m x,rj b[ Si ] ← ∑ j∈S b j mod 2 b1 , b2 ,..., bm がすべて合っていれば i ci ← Bx ( z ⊕ R[ Si ]) ⊕ b[ Si ] x, z = x, z ⊕ R[Si ] ⊕ b[Si ] s ← s + ci この部分はアルゴリズムに問い合わせ x, z = Bx ( z ⊕ R[Si ]) ⊕ b[Si ] 17 If s ≥ 2m 2 then b ← 1 else b ← 0 output b 18 3 2013/06/04 自己訂正（強力版）の評価自己訂正（強力版）の評価 •  が正しいときの失敗確率 b1 , b2 ,..., bm M  2m ! SSC z;r ,...,r ; x,r ,..., x,r x 1 m 1 m Pr # #r ,...,r ←{0,1}n "1 m ( )≠ ⎧⎪1 if Bx ( z ⊕ R[ Si ]) ⊕ ⊕ j∈S x, rj = x, z i X i ( R) = ⎨ 0 otherwise ⎪⎩ x, z :$ &≤ 1 & Mε2 % x, z ⊕ R[Si ] = x, z ⊕ ⊕ j∈S x, rj i Bx ( z ⊕ R[Si ]) = x, z ⊕ R[Si ] これを示そう！ z ⊕ R[ Si ] ∈G 19 自己訂正（強力版）の評価自己訂正（強力版）の評価 •  期待値 z ⊕ R[ S j ] ∈G z ⊕ R[ Si ] ∈G E[ X i ] = Pr[ X i = 1] = Pairwiseに独立 (任意の2つを考えたら独立) r1 r2 r3 r4 Var[ X i ] = E[ X i2 ]− E[ X i ]2 = E[ X i ]− E[ X i ]2 Sj = E[ X i ](1− E[ X i ]) rk = 21 For j ← 1,...,m do rj ←{0,1}n 多数決で失敗 ! Mε $ Pr[ X < M 2] ≤ Pr # X − µ M > & 2 % " チェビシェフの不等式 Pairwise独立でも共分散はゼロ Var[ X 1 ]++Var[ X M ] (M ε 2) 2 = M (1− ε 2 ) / 4 (M ε 2) 2 ≤ 1 Mε2 22 Input: f (x) •  b　が正しいときの　の失敗確率 SSCx 1 , b2 ,..., bm ≤ 1+ ε 1− ε 1− ε 2 ⋅ = 2 2 4 逆計算アルゴリズム Inv 自己訂正（強力版）の評価 1+ ε µ 2 •  分散 rk 一方だけに所属している　が存在するため Si 20 For i ← 0,...,2m −1 b1 bm ← binary representation of i For k ← 1,...,n 可能性をすべて試している！ yk ← SSC x (ek ;r1 ,...,rm ;b1 ,...,bm ) y ← y1  yn 23 If f (x) = f ( y) then x! ← y output x! 24 4 2013/06/04 逆計算アルゴリズム Inv の評価 x •  よい　を仮定していた， 1 ε 1 1 Pr[ Bx (r ) = x, r : r ← {0,1}n ] ≥ + = + 2 2 2 2 p ( n) を思い出そう！ •  そもそもの仮定は， 1 1 Pr[ Bx (r ) = x, r : x ← {0,1}n , r ← {0,1}n ] ≥ + 2 p(n) M  2m Pr "# Inv x (1n ) ≠ x$% ≤ •  •  •  •  n Mε2 Invx SSCx n は　を　回呼び出し SSCx 1 Mε 2 の一回の失敗確率は高々 n Mε 2 どこかの　で失敗する確率は高々 SSCx とすると M = 2nε −2 , m = log( M ) –  の計算時間： Invx O(n3ε −4 ) Invx –  の成功確率：1/2 最後の詰め① Pr[ B( f ʹ′(U n ,U nʹ′ )) = b(U n ,U nʹ′ )] > 25 x •  よい　はどれくらいある？最後の詰め② 1 ε + 2 2 r A Invx •  は　をn回繰り返すアルゴリズム n以下 –  いい　に対して失敗確率は1/2 x r Pr[ A( f (U n )) ∈ f −1 ( f (U n ))] 1 ε + 2 2 1 +ε 2 26 最後の詰め③ x の割合を超える　はどれくらいあるか？ Bx (r ) = x, r 1 1 + 2 p ( n) ≥ Pr[ A( f (U n )) ∈ f −1 ( f (U n )) ∧ U n ∈ GoodX] 1 +ε 2 x = Pr[U n ∈ GoodX]Pr[ AU n (1n ) ∈ f −1 ( f (U n )) | U n ∈ GoodX] x ≥ 1 1 (1 − 2− n ) > 2 p ( n) 4 p ( n) この幅はどれくらいか？ ε 2 ⇒　以上 27 今日のまとめ •  •  •  •  •  28 レポート課題ハードコア述語 Goldreich-Levinの定理チェビシェフの不等式（Pairwise独立な場合）自己訂正アルゴリズム数え上げの議論 f を一方向性関数とする. •  以下で構成される関数を考える f ʹ′( x, r ) def = ( f ( x), r ) x = x1 x2 xn , r = r1r2 rn f ʹ′ は依然として一方向性関数である．これを示せ． •  Good Set と Bad Set を導入するということは，Bxが決定性アルゴリズムであることを実は仮定していた． Bxが確率的アルゴリズムの場合，どのように扱えばよいか検討せよ． 29 30 5