暗号基盤特論 (M43160) ハードコア述語 ハードコア関数 ハードコア述語

2015/07/11
ハードコア述語
• 計算が容易：
暗号基盤特論
–  多項式時間アルゴリズム　が存在して，任意
A
の入力　に対して　は　を出力する
x
A b( x )
予測困難性と識別困難性
(M43160)
• 予測困難：
–  どんな確率的多項式時間アルゴリズム　を考
B
えても，以下の値は無視できる
8 July, 2015
小柴健史
Pr[ B( f (U n ),1n ) = b(U n )] −
1
2
f
b
は　のハードコア述語という！
1
ハードコア関数
2
ハードコア述語とハードコア関数
• 計算が容易：
–  多項式時間アルゴリズム　が存在して，任意
A
の入力　に対して　は　を出力する．ただ
x
A h( x )
し，関数　は長さ正則
h
• 識別困難：
–  どんな確率的多項式時間アルゴリズム　を考
B
えても，以下の値は無視できる
• ハードコア述語は予想困難性の観点で定
義されている
• ハードコア関数は識別困難性の観点で定
義されている．
• にもかかわらず，ハードコア関数はハー
ドコア述語の一般化になっている
–  のとき，両者の定義は一致する
(n) = 1
! )) = 1]
Pr[B( f (U n ),h(U n )) = 1]− Pr[B( f (U n ),U (n)
f
h
は　のハードコア関数という！
3
4
識別困難⇒予測困難
識別困難⇒予測困難
• 以下を仮定する
• アルゴリズム　の成功確率を解析
A
1
Pr[ B( f (U n ),1 ) = b(U n )] > + ε
2
n
Pr[ A( f (U n ), h(U n )) = 1] − Pr[ A( f (U n ), U1 )) = 1]
f ( x), h( x)
• このとき，　を入力とする以下の
アルゴリズム　を考える
A
B( f ( x))
–  を走らせ，　と一致していれば１
h( x )
= Pr[ B( f (U n )) = h(U n )] − Pr[ B( f (U n )) = U1 ]
≥
を出力し，そうでなければ０を出力する
–  は識別アルゴリズムになっている！
A
1
1
+ε − = ε
2
2
予測できるなら区別できる！
5
6
1
2015/07/11
予測困難⇒識別困難
よい入力の判定？
• 以下を仮定する
Pr[ B( f (U n ), h(U n )) = 1] − Pr[ B( f (U n ), U1 )) = 1] > ε
f ( x)
• このとき，　を入力とする以下のアルゴ
リズム　を考える
A
–  p
の確率を見積もる
1 = Pr[ B( f ( x),1) = 1]
–  の確率を見積もる
p0 = Pr[ B( f ( x),0) = 1]
–  差が小さいときにはランダムに出力
p1 > p0
–  のとき１を出力，それ以外は０を出力
• （後で確かめるが）よい入力はそんな
に沢山はない
• 我々の目的は予測アルゴリズムの構成
–  予測の成功は，半分以上の確率で有意に予
測すること．
–  悪い入力に対して，予測確率が1/2を達成
すれば，なんとかなる．
–  「よい・悪い」の判定が必要．その判定に
もとづいてアルゴリズムの動作を変える．
7
予測困難⇒識別困難
8
予測困難⇒識別困難
まず，
Pr[ B( f (U n ), U1 )) = 1]
Pr[ B( f (U n ), h(U n )) = 1]
= Pr[U1 = h(U n )]Pr[ B( f (U n ), U1 )) = 1| U1 = h(U n )]
+ Pr[U1 = h(U n )]Pr[ B( f (U n ), U1 )) = 1| U1 = h(U n )]
(
±ε 2
>ε
)
= Pr[ B( f (U n ), h(U n )) = 1] + Pr[ B( f (U n ), h(U n )) = 1] 2
Pr[ B( f (U n ), U1 ) = 1]
>ε
>ε
なので
Pr[ B( f (U n ), h(U n )) = 1] − Pr[ B( f (U n ), h(U n )) = 1] > 2ε
±ε 2
Pr[ B( f (U n ), h(U n )) = 1]
さらに，とりあえず，以下を仮定（★）
Pr[ B( f (U n ), h(U n )) = 1] − Pr[ B( f (U n ), h(U n )) = 1] > 2ε
9
予測困難⇒識別困難
10
数え上げの議論
次に
乱数
Pr[ B( f (U n ), h(U n )) = 1] − Pr[ B( f (U n ), h(U n )) = 1] > 2ε
１
は平均的な入力に対する評価なので，よい　x
を
Pr[ B( f ( x), h( x)) = 1] − Pr[ B( f ( x), h( x)) = 1] > ε
を満たすものとする．このような　は少な
x
くとも　の割合存在する
ε
０
１
入力
2ε
面積：
11
12
2
2015/07/11
数え上げの議論
予測困難⇒識別困難
• よい　に対して，　x
p1 = Pr[ B( f ( x),1) = 1]
と　p0 = Pr[ B( f ( x),0) = 1]
乱数
１
を精度　で見積もる
±ε 8
p0
• （　の）推定アルゴリズム
–  を　回実行し，　と
B( f ( x), 0) k
B( f ( x), 0) = 1
なった回数を　とおくとき，推定値は
s

p =s k
ε
０
ε
１ 入力
2ε
面積：
0
13
推定アルゴリズムの評価
予測困難⇒識別困難
• よい　では
p0 − p1 ≥ ε
x
• このとき
ε
p0 − 
p0 ≥
8
となる確率は極めて小さい！　Hoeffding Bound：
• 高い確率で（確率　で）　(1 − 2− n−1 )2 > 1 − 2− n
ε
ε
p0 − 
p0 <
p1 − 
p1 <
8
8
k
%
(
'
*
2 2
−2k
δ
*
Pr X − E[ X ] ≥ δ ≤ 2exp ' k
'
*
' ∑ (bi − ai ) *
& i=1
)
• 高い確率で，

p0 > 
p1
–  なら　このとき予測値 = 0
p0 > p1


–  なら　このとき予測値 = 1
p0 < p1
p0 < p1
X i ∈ [ai , bi ], X = ∑ X i k
i =1
(
)
k　とおけばよい
= 32(n + 2) ε 2 log e
14
予測は正しい！
15
予測困難⇒識別困難
16
よい入力，わるい入力
Pr[ B( f ( x), h( x)) = 1]
• よい　では，高い確率で
x
3ε

p0 − 
p1 >
4
• これを満たさないとき，　が悪いと判断
x
よい入力の場合
+ε 2
+ε 4
–  判定しようがないのでランダムビットを出力
−ε 4
−ε 2
3ε

p0 − 
p1 >
4
悪い入力の場合
3ε

p0 − 
p1 ≤
4
グレーゾーンの場合
ε   5ε
< p0 − p1 ≤
4
4
高確率で正しい判定
17
Pr[ B( f ( x), h( x)) = 1]
18
3
2015/07/11
予測困難⇒識別困難
予測困難⇒識別困難
全体での評価する！
E:
推定アルゴリズムが失敗しない
• よい入力の場合
–  必ず予測フェーズに入り，その予測値は正し
い
• 悪い入力の場合
Pr[ A( f (U n )) = h(U n )]
–  必ず，ランダム予測を行う
= Pr[ E ]Pr[ A( f (U n )) = h(U n ) | E ]
• グレーゾーン入力の場合
+ Pr[¬E ]Pr[ A( f (U n )) = h(U n ) | ¬E ]
–  予測フェーズに入る場合もあれば，ランダム
予測する場合もある
–  予測フェーズに入った場合は，その予測値は
正しい
−n
≥ (1 − 2 ) Pr[ A( f (U n )) = h(U n ) | E ]
19
20
予測困難⇒識別困難
予測困難⇒識別困難
• よい入力の場合
Pr[ A( f ( x)) = h( x) | E, x ∈ G] = 1
• 悪い入力の場合
Pr[ A( f (U n )) = h(U n ) | E ]
= Pr[U n ∈ G ]Pr[ A( f (U n )) = h(U n ) | E ,U n ∈ G ]
Pr[ A( f ( x)) = h( x) | E, x ∈ B] = 1 2
+ Pr[U n ∈ B]Pr[ A( f (U n )) = h(U n ) | E ,U n ∈ B]
• グレーゾーン入力の場合
+ Pr[U n ∈ M ]Pr[ A( f (U n )) = h(U n ) | E ,U n ∈ M ]
Pr[ A( f ( x)) = h( x) | E, x ∈ M] ≥ 1 2
≥ ε + (1 − ε ) 2
=1 2+ε 2
21
22
予測困難⇒識別困難
予測困難⇒識別困難
まとめると，
以下の仮定（★）を思い出そう！
Pr[ B( f (U n ), h(U n )) = 1] − Pr[ B( f (U n ), h(U n )) = 1] > 2ε
Pr[ A( f (U n )) = h(U n )]
≥ (1 − 2− n )(1 2 + ε 2) ≥ 1 2 + ε 3
実は，
Pr[ B( f (U n ), h(U n )) = 1] − Pr[ B( f (U n ), h(U n )) = 1] > 2ε
識別できるなら予測できる！
23
かもしれない．この場合，
Pr[ A( f (U n )) ≠ h(U n )] ≥ 1 2 + ε 3
A
が示せて，　の結果を反転するアルゴリズ
ム　を考えればよい．
A
24
4
2015/07/11
まとめ
• ハードコア述語の一般化：ハードコア関
数
• ハードコア関数の特殊ケースとハードコ
ア述語の等価性
次回
• ハードコア関数の構成方法
• ＸＯＲ補題
25
5