一方向関数とランダムオブジェクト - 暗号理論教室

---

一方向関数

順方向は効率的に計算できるが、逆方向は決して効率的に計算できない関数を一方向関数という。
すなわち、

定義(一方向関数)
関数 f: {0,1}* → {0,1}* が一方向関数であるとは、

• ある効率的なアルゴリズムMがあって、どのようなxについてもM(x) = f(x).
• どのような効率的なアルゴリズムAについても、その成功確率
  • Pr[ x ← {0,1}ⁿ, x' ← A(1ⁿ, f(x)) : f(x') = f(x) ]
• がネグリジブル

であることをいう。

定義(RSA仮定)
どのような効率的なアルゴリズムAについても、確率

• Pr[ (N, e, d) ← GenRSA(1ⁿ), x ← Z_N*, y = x^e mod N : A(N, e, y) = x ]

は（nについて）ネグリジブルである、という仮定をアルゴリズムGenRSAに関するRSA仮定と呼ぶ。

RSA仮定のもとで、RSA関数 f_e,N(x) = x^e mod N は一方向関数である。

定義(離散対数仮定)
どのような効率的なアルゴリズムAについても、確率

• Pr[ (q, g) ← GenG(1ⁿ), x ← Z_q, y = g^x : A(q, g, y) = x ]

は（nについて）ネグリジブルである、という仮定をアルゴリズムGenGに関する離散対数仮定と呼ぶ。

離散対数仮定のもとで、離散指数関数 f_q,g(x) = g^x は一方向関数である。

疑似乱数生成器

真の乱数をそれより長い疑似的な乱数に拡大する効率的な変換を疑似乱数生成器と呼ぶ。
すなわち、

定義
l(n)をnの多項式とする。
関数G : {0,1}ⁿ → {0,1}^l(n) が疑似乱数生成器であるとは、

• ある効率的なアルゴリズムMがあって、どのようなsについてもM(s) = G(s)であり、
• 任意の効率的なアルゴリズムDについて、その識別利得
  • ｜ Pr[r ← {0,1}^l(n) : D(r) = 1] - Pr[s ← {0,1}ⁿ : D(G(s)) = 1] ｜
• はネグリジブル

であることをいう。

• 上のを拡大因子とよぶ。
• Gが疑似乱数生成器ならばGは一方向関数である。

ハードコア述語

一方向関数fが確実に隠す、原像の1ビットをハードコア述語という。すなわち、

定義
述語hc : {0,1}* → {0,1} が（一方向）関数f : {0,1}* → {0,1}* のハードコア述語であるとは、

• ある効率的なアルゴリズムMがあって、どのようなxについてもM(x) = hc(x)であり、
• 任意の効率的なアルゴリズムAについて、その識別利得
  • ｜ Pr[x ← {0,1}ⁿ : A(f(x)) = hc(x)] - 1/2 ｜
• はネグリジブルであることをいう。

• 関数fがハードコア述語をもてば、fは一方向関数。

ハードコア述語の存在

ジェネリックケース

一方向関数の原像のランダムビットの総和はそのハードコア述語である。
すなわち、

定理 (Goldreich-Levin) [GL 89]
f:{0,1}ⁿ → {0,1}ⁿ を一方向関数とする。
このとき、g(x,r) = (f(x), r)も一方向関数となるが、

• gl(x,r) = Σ_i=1..n(x_i r_i)

はそのハードコア述語である。

系
一方向関数が存在するならば、ハードコア述語をもつ一方向関数が存在する。

RSA関数のハードコア

RSA仮定のもとで、パリティはRSA関数のハードコア述語である：

• パリティ Lsb(x) =^def xの最下位ビット.

定理(RSA-HC1)
(n, e, d) ← GenRSA(1^k) とする。
ある確定的なPTアルゴリズムA₁があって、任意のx ∈ Z_n*, y = x^e mod n について

• A₁(n, e, y) = Lsb(x)

ならば、ある確定的なPTアルゴリズムA₂があって、任意のx ∈ Z_n*, y = x^e mod n について

• A₂(n, e, y) = x

である。

証明

定理(RSA-HC2)
あるPPTアルゴリズムA₁とある多項式ξがあって、

• Pr[ x ← Z_n*, y = x^e mod n : A₁(n, e, y) = Lsb(x) ] ≧ (1/2) + (1/ξ(l))

ならば（l=|n|）、あるPPTアルゴリズムA₂とある正の定数cがあって、

• Pr[ x ← Z_n*, y = x^e mod n : A₂(n, e, y) = x ] ≧ c

である。

証明

離散指数関数のハードコア

gを素数pを法とする原始元とする。離散対数仮定のもとで、最上位ビットは、離散指数関数f_p-1,g(x) = g^x mod pのハードコア述語である。ここで、離散対数xの最上位ビットとは、xが(p-1)/2以上であるか否かを表す。
（ヒント： h = g^{x_l...x₁x₀}に対し、(h g^-x₀)^1/2 = g^0x_l...x₁。ここで、1/2乗の符号が問題。）

疑似乱数生成器の存在

一方向置換とそのハードコア述語によって、真の乱数を、それより1ビットだけ長い疑似乱数に変換することができる。
すなわち、

定理(PSG)
f : {0,1}ⁿ→{0,1}ⁿ を一方向置換とし、hcをそのハードコア述語とするならば、
関数G(s) = (f(s), hc(s))は拡大因子の疑似乱数生成器である。

証明

1ビットさえ長くできれば、それを繰り返すことによって、いくらでも長い疑似乱数を生成することができる。
すなわち、

構成(PSG2)
G₀ : 拡大因子l₀(n)=n+1の疑似乱数生成器
p(n): nより大きい任意の多項式, p'(n) := p(n) - n

G: s (∈{0,1}ⁿ) を入力として、     /* 先頭nビットに繰り返しG₀を適用する */

• s₀ = s
• i ∈ [1..p'(n)] :
  • (s'_i-1, σ_i-1) = s_i-1      /* s'_i-1はs_i-1の先頭nビットをとる */
  • s_i = (G₀(s'_i-1), σ_i-1)      /* s_iはn+iビットとなる */
• return s_p'(n)

定理(PSG2)
p(n)をnより大きい任意の多項式とする。
G₀が拡大因子l₀(n)=n+1の疑似乱数生成器ならば、
構成(PSG2)のGは、多項式p(n)を拡大因子l(n)とする疑似乱数生成器である。

証明

定理(PSG1)と定理(PSG2)より、以下の構成(PSG3)の G: {0,1}ⁿ → {0,1}^p(n) は疑似乱数生成器である。

構成(PSG3)
p(n): nより大きい任意の多項式, p'(n) := p(n) - n
f : {0,1}ⁿ → {0,1}ⁿ : 一方向置換
hc : {0,1}ⁿ → {0,1} : fのハードコア述語

• G(s) = (f^p'(n)(s), hc(f^p'(n)-1(s)), ..., hc(s))

• 以上より、一方向置換が存在するならば、疑似乱数生成器が存在することがわかった。
• 一方向関数が存在するならば、疑似乱数生成器が存在することが示されている。

疑似ランダム関数

ある関数が、その入力値と出力値の組み合わせからは、ランダム関数と区別できないとき、それを疑似ランダム関数という。
すなわち、

定義
F : {0,1}* x {0,1}* → {0,1}* を効率的に計算可能で、長さ保存の、鍵付き関数であるとする。
Fが疑似ランダム関数であるとは、

• 任意の効率的なアルゴリズムDについて、その識別利得
  • ｜ Pr[k ← {0,1}ⁿ : D^F(k,・)(1ⁿ) = 1] - Pr[f ← Fnc(n,n) : D^f(・)(1ⁿ) = 1] ｜
• がネグリジブル

であることをいう。ここで、Fnc(n,n)はnビット入力nビット出力のすべての関数の集合を表す。

真の乱数の長さを2倍にする疑似乱数生成器があれば、疑似ランダム関数を構成できる。
すなわち、

構成(PSF)
拡大因子l(n)=2nの疑似乱数生成器G=(G₀,G₁)を用いて、鍵付き関数Fを構成する：

• k ∈ {0,1}ⁿ について
• F(k, (x₁,x₂,・・・,x_n)) =^def G_{x_n}(・・・(G_{x_2}(G_{x_1}(k)))・・・).

構成(PSF)はnビット入力x=(x₁,x₂,・・・,x_n)に対し、レベルnの2分木を構成し各ノードにGを用いて疑似乱数を割り当てている。
ラベルxをもつ葉ノードに割り当てられた疑似乱数がF(k,・)のxにおける値となる。

定理(PSF)
Gが拡大因子l(n)=2nの疑似乱数生成器ならば、構成(PSF)の鍵付き関数Fは疑似ランダム関数である。

証明

上へ

---