Document

2015/07/11
本日の内容
• 計算論的識別不可能性
–  1サンプルｖｓ多サンプル
–  ハイブリッド法
暗号基盤特論 計算論的識別不可能性とハイブリッド法 (M43160)
• 非一様計算モデル
–  計算論的識別不可能性
–  非一様帰着
8 July, 2015
小柴健史
1
2
距離
統計的距離
X n }nn∈･
•  {　，　：確率分布族の統計的距離
∈N {Yn }n
n∈
∈･N
距離の公理
Δ( X ,Y ) ＝

–  Δ( X , Y ) = 0 ⇔ X = Y
–  Δ( X , Y ) ≥ 0
Δ( X , Y ) = Δ(Y , X )
–  –  Δ( X , Y ) + Δ(Y , Z ) ≥ Δ( X , Z )
（三角不等式）
1
∑ Pr[ X n = α ]− Pr[Yn = α ]
2 α
• αの種類の次元を持つベクトルと考える
• たとえば
d
k
∑x −y
i
k
i
i=1
3
統計的距離
確率分布族
I ：可算インデックス集合
• 　• {　X　：確率変数の系列
i }i∈I
• 具体例
–  普通のサイコロ　X
(1 6,1 6,1 6,1 6,1 6,1 6)
–  １の目が出易いサイコロ Y
• 多くの場合，可算インデックス集合は
(1 2,1 10,1 10,1 10,1 10,1 10)
–  自然数集合
–  の部分集合
{0,1}*
–  その統計的距離
1 ⎛ ⎛ 1 1 ⎞ ⎛ 1 1 ⎞ ⎞ 1
Δ( X , Y ) = ⎜ ⎜ − ⎟ + 5 ⎜ − ⎟ ⎟ =
2 ⎝ ⎝ 2 6 ⎠ ⎝ 6 10 ⎠ ⎠ 3
つまり、確率変数の値域の大きさの次元のベク
トルに対する　距離　
1
4
5
6
1
2015/07/11
多項式時間識別不可能
ハードコア関数，再訪
X n }nn∈･
Yn }nn∈･
•  {　,
：確率分布族が多項式時
∈N {
∈N
間識別不可能であるとは，任意の確率的多
項式時間アルゴリズム　に対して以下の
D
値が無視できるときをいう
Pr[ D( X n ,1n ) = 1] − Pr[ D(Yn ,1n ) = 1]
• 前回と別の言葉で定義を与える
f
h が　のハードコア関数であるとは
• 　{( f (U n ), h(U n ))}n∈･
と {( f (U n ), U lʹ′( n ) ))}nn∈∈･N
∈N
が計算論的識別不可能であるときをいう　• 計算論的識別不可能ともいう
7
識別不可能性
8
多項式時間サンプラブル
• 統計的識別不可能とは，統計的距離が無
視できるときをいう
• 計算論的識別不可能とは，任意の確率的
アルゴリズム　を適用した後の　D
D( X n )
と　とが統計的に識別不可能なことを
D(Yn )
いう
X = { X n }nn∈∈･N
•  が多項式時間サンプラブルで
あるとは確率的多項式時間アルゴリズム　S
が存在して，すべての　で　と　と
S (1n ) X n
n
が統計的距離０であるときをいう。
9
10
多項式個サンプリング
１サンプル vs 多サンプル
•  と　が多項式時間サ
X = { X n }nn∈∈･N Y = {Yn }n∈∈･N
ンプラブルであるとする．多項式個サンプ
リングによって識別不可能であるとは，任
意の確率的多項式時間アルゴリズム　と
D
m
任意の多項式　に対して，以下が無視で
きるときをいう
= { X n }n∈･ Y = {Yn }n∈･
•  X　と　を多項式時間サン
プラブルであるとすると，以下は同値
–  X , Yが計算論的識別不可能
–  X , Yが多項式時間サンプリングによって
も計算論的識別不可能
Pr[ D( X n(1) ,..., X n( m( n)) ) = 1] − Pr[ D(Yn(1) ,..., Yn( m( n)) ) = 1]
X n(1) ,..., X n( m ( n ))
X n( i )
• ただし　は独立で，各　は
確率分布として　と一致する（i.i.d.）
Xn
11
12
2
2015/07/11
証明
D
• あるアルゴリズム　と多項式　が存在
m, p
Pr[ D( X n(1) ,..., X n( m( n )) ) = 1] − Pr[ D(Yn(1) ,..., Yn( m( n )) ) = 1] >
• ここで，以下の分布を導入する
混合分布
1
p ( n)
H nk ＝
 ( X n(1) ,..., X n(k ) ,Yn(k+1) ,...,Yn(m) )
• このとき，
H n6
Xn
Xn
Xn
Xn
Xn
Xn
H n4
Xn
Xn
Xn
Xn
Yn
Yn
どれか一つは
距離d/3以上
距離d
H nm = ( X n(1) ,..., X n( m ) )
H n2
H n0 = (Yn(1) ,..., Yn( m) )
• つまり，　は中間的な分布になっている
H nk
（ハイブリッドアーギュメント）　13
H n0
Xn
Xn
Yn
Yn
Yn
Yn
Yn
Yn
Yn
Yn
Yn
Yn
証明
証明
Dʹ′
• アルゴリズム　オブザベーション
–  目的：１サンプルを区別する
–  入力：α ← X n or Yn
k ∈ {0,..., m − 1}
–  を一様に選択
x1 ,..., xk ← ( X n ) k , yk + 2 ,..., ym ← (Yn ) m−k −1
–  D( x1 ,..., xk , α , yk +2 ,..., ym )
–  を呼び，そのまま出力
Dʹ′
14
1 m −1
∑ Pr[ D( H nk +1 ) = 1]
m k =0
1 m −1
Pr[ Dʹ′(Yn ) = 1] = ∑ Pr[ D( H nk ) = 1]
m k =0
Pr[ Dʹ′( X n ) = 1] =
D
Xn
α ← X n or Yn
Yn
15
証明
ハイブリッド法
このとき
• 確率分布間には距離が定義されている
• 中間確率分布の個数は少ない(多項式個)
• 各中間確率分布の差は非常に小さい
• 中間確率分布をうまく設定することによ
り証明が成立するようにできる
Pr[ Dʹ′( X n ) = 1] − Pr[ Dʹ′(Yn ) = 1]
=
1
m
m −1
∑ Pr[ D( H
k +1
n
16
) = 1] − Pr[ D( H nk ) = 1]
k =0
1
= Pr[ D( H nm ) = 1] − Pr[ D( H n0 ) = 1]
m
1
≥
mp (n)
–  今回の例は非常に単純な構成方法！
17
18
3
2015/07/11
非一様計算
非一様計算
• 通常のアルゴリズムは一様計算と呼ばれ
る
• 論理回路における基本素子
–  問題のサイズに依存しないため
• 一方，問題のサイズごとに問題を解く方
法が変化することが許容される場合，非一
様計算アルゴリズムと呼ばれる
–  例えば，n変数ブール関数を計算する場合，変
数の個数毎にブール関数を計算する論理回路　Cn
が存在してもいい．アルゴリズムと対比する
意味でも，回路の族　として表記され
{Cn }nn∈･∈N
る
19
ＡＮＤ素子　ＯＲ素子
x y x ∧ y x ∧ y
x y x∨ y
0 0
0
0 0
0
0
1 0
1 0
1
0 1
0
0 1
1
x y
1 1
1
1 1
1
ＮＯＴ素子 x ¬x
0
1
回路族
1
0
x∨ y
x y
¬x
x
20
回路族とアルゴリズム
(1 )
•  A
の出力が　の記述であるとき，族　{Cn }nn∈･
Cn
∈N
は一様回路族と呼ばれる
–  が多項式アルゴリズムであるとき　のサイズは
Cn
A
n
Cn
Cn +1
多項式になる．また，その評価（回路値の計算）
は多項式時間で可能
–  多項式時間一様な多項式サイズ回路族は多項式時
間アルゴリズムと等価
‥‥
‥‥
‥‥
n 変数
‥‥
n +1
変数
• 単に多項式サイズ回路族といった場合，多項
式時間アルゴリズムよりも能力が高い
21
回路族とアルゴリズム
–  暗号理論においては，敵対者の能力は多項式サイ
ズ回路族であることを想定する場合も多い
22
回路族とアルゴリズム
• 確率的多項式時間アルゴリズムとの対比から，
乱数入力多項式サイズ回路族という概念もあ
る
• ただし，通常の多項式サイズ回路族と能力は
同等である
–  最も，多くの割合の入力に対して計算が正しくな
るような乱数が存在する
–  上記のよい乱数入力を回路に直接ハードワイヤー
することにより，乱数部分を固定化できる
23
• 今　か否かを判定したいとする
x∈L
• 一様計算では　となる　の存在性
A( x) = χ L
A
や　の用いる資源を議論する
A
• 非一様計算では，　となる
A( x, a(| x |)) = χ L
アルゴリズム　や入力の長さだけで決まる
A
a
助言関数　の存在性を議論する
–  は長さ　専用の回路の記述
a (| x |)
|x|
A
–  は回路値の計算アルゴリズム
–  の計算資源は問わない
a
24
4
2015/07/11
回路族とアルゴリズム
多項式時間識別不可能
x∈L
• 今　か否かを判定したいとする
• 一様計算では　となる　が多項式
A
A( x) = χ L
時間で動作するとき，この判定問題は計算
量クラスPに属する
A( x, a(| x |)) = χ L
• 非一様計算では，　となる多
項式時間アルゴリズム　と入力の長さだけ
A
a
で決まる多項式長の助言関数　が存在する
とき，この判定問題は計算量クラスP/
polyに属する
X n }nn∈･
Yn }nn∈･
•  {　,
：確率分布族が多項式時間
∈N {
∈N
識別不可能であるとは，任意の確率的多項
式時間アルゴリズム　に対して以下の値
D
が無視できるときをいう
Pr[ D( X n ,1n ) = 1] − Pr[ D(Yn ,1n ) = 1]
• 計算論的識別不可能ともいう
–  多項式サイズ回路計算可能な判定問題のクラ
スはP/polyに一致する
25
多項式サイズ回路族識別不可能
X n }nn∈･
Yn }nn∈･
•  {　,
：確率分布族が多項式サイ
∈N {
∈N
ズ回路族識別不可能であるとは，任意の多
項式サイズ回路族　に対して以下の
{Dn }nn∈･
∈N
値が無視できるときをいう
Pr[ Dn ( X n ) = 1] − Pr[ Dn (Yn ) = 1]
26
多項式個サンプリング
X = { X n }nn∈∈･N Y = {Yn }nn∈∈･N
•  と　が確率分布族と
する．多項式個サンプリングによって非一
様計算識別不可能であるとは，任意の多項
{Dn }nn∈･
式サイズ回路族　と任意の多項式　m
∈N
に対して，以下が無視できるときをいう
Pr[ Dn ( X n(1) ,..., X n( m( n)) ) = 1] − Pr[ Dn (Yn(1) ,..., Yn( m( n)) ) = 1]
• これを非一様計算論的識別不可能と呼ぼ
う（一般的な呼称ではない）
• ただし，　は独立で、各　は
X n(1) ,..., X n( m ( n ))
X n( i )
確率分布として　と一致する
Xn
27
１サンプル vs 多サンプル
28
証明の概略
X = { X n }nn∈∈･N Y = {Yn }nn∈∈･N
•  と　を確率分布族と
する．このとき，以下は同値
–  X , Yが非一様計算論的識別不可能
– X　, Yが多項式個サンプリングによっても
• ある多項式サイズ回路族　と多項
{Dn }nn∈･
∈N
m, p
式　が存在し
Pr[ Dn ( X n(1) ,..., X n( m( n )) ) = 1] − Pr[ Dn (Yn(1) ,..., Yn( m ( n )) ) = 1] >
非一様計算論的識別不可能
1
p ( n)
• また，以前に定義した中間確率分布で
Pr[ D( H nk +1 ) = 1] − Pr[ D( H nk ) = 1]
の値が最も大きくなる　を　とおく　k kn
29
30
5
2015/07/11
証明の概略
まとめ
• 回路　Dnʹ′
–  目的：１サンプルを区別する
–  入力：α ← X n or Yn
–  以下の確率の差
非一様帰着
Pr[ D( H nkn +1 ) = 1] − Pr[ D( H nkn ) = 1]
• 計算論的識別不可能性
• 1サンプルｖｓ多サンプル
• ハイブリッド法
• 非一様計算
が最も大きくなるような
x1 ,..., xkn ∈ supp(X n )kn , ykn +2 ,..., ym ∈ supp(Yn )m−kn −1
について Dn ( x1 ,..., xkn , α , ykn + 2 ,..., ym )
を計算する回路が　である
Dnʹ′
31
32
6

Download Report