



I240 暗号理論 2019
一方向性関数、擬似乱数生成器、擬似ランダム関数 (1)2019/10/30, 11/1 講師 藤崎

1 はじめに
現代暗号理論の基礎概念である一方向性関数 (one-way function)、擬似乱数生成器 (pseudo-random(number) generator)、擬似ランダム関数 (pseudo-random function) を中心に現代暗号理論の根底を流れる考え方や証明法に慣れることを目的とする。一方向性関数、擬似乱数生成器、擬似ランダム関数の存在は全て等価である。なかでも特に知っておくべきは、Goldreich-Levin のハードコア述語の構成法、擬似乱数生成器の伸長定理、Goldreich-Golidwasser-Micali の擬似乱数生成器から擬似ランダム関数の構成法である。

2 よく使われる用語と定義■確率的アルゴリズム アルゴリズム M が確率的であるとは、M の出力 y が入力 x と M の内部コイン投げr ∈ {0, 1}∗ によって決定される時に言う。すなわち、M は二入力関数として M (x, r) = y と書ける。任意の（サイズ n の）入力 x ∈ {0, 1}n に対して、（確率的）アルゴリズム M が常に時間 t(n) で停止する時、M をt(n)-時間（確率的）アルゴリズムと呼ぶ。M (x) は M の内部コイン投げによって定められる確率変数と思って良いので，Pr[M (x) = y] が定義できる。M の動作時間が限定されている時（例えば，t(n)-時間確率的アルゴリズムの時）内部コイン投げは有限なので一般性を失うことなく r ∈ {0, 1}m(n) として、

Pr[M (x) = y] =#{r ∈ {0, 1}m(n) |M (x, r) = y}2m(n)と考えてよい。ここで，t(·), m(·) は，N → N の関数。確定的 (deterministic) なアルゴリズムは内部コインの無い確率的なアルゴリズムの特別な場合として定義できる。
関数 t : N → R+ が多項式制限である (polynomial-bound) とは、十分大きな全ての n に対して，t がある多項式により上から抑えられることを言う。すなわち、ある c > 0、ある正整数 n0 が存在して、全ての n ≥ n0に対して t(n) ≤ nc が成り立つことを言う。これを、しばしば t(n) = O(poly(n)) と書く。
アルゴリズム M が確率的多項式時間アルゴリズム (probabilistic polynomial-time (PPT) algorithm) であるとは、M が t(n)-時間（確率的）アルゴリズムで，t(n) がある多項式制限であることを言う。特に確定的多項式時間アルゴリズムであることを強調したいときは、deterministic polynomial-time (DPT) algorithm と書く。
注釈 1

我々は確率的アルゴリズムを主に扱うので、deterministic アルゴリズムをその対比で確定的アルゴリズムと呼ぶことにする（確定的（deterministic）⇔ 確率的（probabilistic））。この訳語は非標準的で，通常非決定性アルゴリズムとの対比から決定性アルゴリズムと良く訳されている（決定性（deterministic）⇔ 非決定性（non-deterministic））。
■一様/非一様なアルゴリズム

Turing 機械のように, 任意の長さの入力を受け付けるアルゴリズムを一様(uniform) なアルゴリズムという。一方, ある固定の長さの入力に対してのみ動作するアルゴリズムを非一様 (non-uniform) なアルゴリズムと呼ぶ。Mn を長さ n の問題に対してのみ動く確率的アルゴリズムとしてM := (M1 , . . . , Mn , . . .) = (Mn )n>0 のように非一様 (non-uniform) なアルゴリズムの族 M を定義する。非1一様な多項式時間アルゴリズム（の族）の力は、多項式サイズの回路（の族）と等しい。非一様な多項式時間アルゴリズムの族は、多項式時間制限の Turing 機械 T とその T に長さ n ごとに与えられる（n の）多項式の長さの補助入力 zn の組の族 (T, zn )n>0 であらわすことが出来る。
暗号の世界では一般に敵 (adversary) を非一様な確率的多項式時間アルゴリズムの族とみなす。以下、敵、識別器などは特に断らなくても非一様なアルゴリズム（の族）とみなす。
■無視できる関数 関数 ϵ : N → R+ が無視できる (negligible) とは，ϵ がいかなる多項式（の逆数）より早く0 に収束する時に言う：すなわち，任意の c > 0 に対して，ある正整数 n0 が存在して，全ての n ≥ n0 に対して ϵ(n) ≤ n−c が成り立つことを言う。別の言い方をすると、ϵ(n) が無視できる関数とは ϵ(n) = n−ω(1) *1 。
■統計的識別不可能性

X = (Xn )n>0 を {0, 1}n 上に値をとる確率変数 Xn の族とする。二つの確率変数の族 X = (Xn )n>0 , Y = (Yn )n>0 の統計的距離をDist(Xn , Yn ) :=12∑

| Pr [Xn = a] − Pr[Yn = a]|
Xna∈{0,1}nYnと定義する。ある無視できる関数 ϵ(n) があって, 十分大きな全ての n で，Dist(Xn , Yn ) ≤ ϵ(n) が成立する
時，二つの確率変数の族 X, Y は, 統計的識別不可 (statistically indistinguishable) と言う（ X ≈s Y と書く）。
特に, 全ての n に対して, Dist(Xn , Yn ) = 0 の時, X, Y は, 完全識別不可 (perfectly indistinguishable) と言う（ X ≡ Y ）。
■計算量的識別不可能性

X = (Xn )n>0 を {0, 1}n 上に値をとる確率変数 Xn の族とする。D : {0, 1}∗ →{0, 1} を（非一様な）t(n)-時間確率的アルゴリズムの族とする。二つの確率変数の族 X = (Xn )n>0 , Y =(Yn )n>0 に対して，D の識別能力をDistD (Xn , Yn ) := | Pr [D(Xn ) = 1] − Pr [D(Yn ) = 1]|D,YnD,Xnで定義する。ここで PrD,Xn [· · · ] とは，確率が D, Xn にのみ依存することの強調であり，特に確率がどのような分布に依存するか明らかな時は省略する。二つの確率変数族 X, Y が, (t, ϵ)-識別不可 (indistinguishable)とは, 全てのの t(n)-時間 PPT D に対して, 十分大きな全ての n で, DistD (Xn , Yn )(n) ≤ ϵ(n) が成立することである（X ≈(t,ϵ) Y と書く）。全ての多項式制限の関数 t(n) に対して, ある無視できる関数 ϵ(n) が存在して, X ≈(t,ϵ) Y のとき, 確率変数の族 X と確率変数の族 Y は計算量的識別不可 (computationallyindistinguishable) という（ X ≈c Y と書く）。
注釈 2 DistD (Xn , Yn ) とは確率変数 D(Xn ) と D(Yn ) の統計的距離 Dist(D(Xn ), D(Yn )) に等しい。

DistD (Xn , Yn ) = | Pr [D(Xn ) = 1] − Pr [D(Yn ) = 1]|
D,Xn

D,Yn1 ∑=| Pr [D(Xn ) = a] − Pr [D(Yn ) = a]|2
D(Xn )
D(Yn )
a∈{0,1}= Dist(D(Xn ), D(Yn )).

*1

f (n)

f = ω(g) if and only if limn→∞ g(n) = +∞2

3 一方向性関数とハードコア述語
3.1 一方向性関数 (One-Way Function)関数 f : {0, 1}∗ → {0, 1}∗ を考える。(a) 任意の x に対して，x の長さの多項式制限時間で f (x) を計算する確定的アルゴリズムが存在する一方で，(b) f −1 (y) を計算するのが平均的に難しい時，f を一方向性関数(one-way function) と呼ぶ。
より正確には, t(n)-時間アルゴリズムの敵 A の f の逆計算に関する成功確率を，

AdvowfA,f (n) :=[A(f (x)) ∈ f −1 (f (x))]

Prx←R {0,1}n ,A= Pr [A(f (Un )) ∈ f −1 (f (Un ))]Un ,Aと定義する。ここで，Un は {0, 1}n 上の一様分布に従う確率変数である。A の成功確率は，A の内部コインと入力 x の {0, 1}n 上の一様分布に依存する（つまり，A による f の逆計算の平均的な難しさを定義している）。
条件 (a) を満足する関数 f : {0, 1}∗ → {0, 1}∗ が，任意の t(n)-時間確率的アルゴリズム A に対して，十分大きな全ての n で Advowf
A,f (n) ≤ ϵ(n) が成り立つ時，関数 f を，(t(n), ϵ(n))-一方向性関数（又は，(t(n), ϵ(n))-OWF ）と呼ぶ。
特に，t(n) が多項式制限で，ϵ(n) が無視できる関数の時，関数 f を一方向性関数と呼ぶ。
現実に我々が知っている一方向性関数の候補はこの定義にやや合致しない。そこで, 代わりに一方向性関数の族 F = {fi }i∈I を次のように定義する。(a) 全ての インデックス i ∈ In (= I ∩ {0, 1}n ) に対して, 関数

fi : {0, 1}n → {0, 1}∗ が定義される。fi は多項式時間で計算できる（一様な確定的多項式時間アルゴリズムで fi を実装できる）。

(b) t(n)-時間アルゴリズムの敵 A の成功確率を，−1nAdvowf
A,F (n) := Pr[i ←R In ; x ←R {0, 1} : A(fi (x)) ∈ fi (fi (x))]と定義したとき, 任意の t(n)-時間確率的アルゴリズム A に対して，十分大きな全ての n で Advowf
A,F (n) ≤ ϵ(n)が成り立つ。条件 (a), (b) を満たす関数族 F を，(t(n), ϵ(n))-一方向性関数族と呼ぶ。特に，t(n) が多項式制限で，ϵ(n) が無視できる関数の時，関数 f を一方向性関数族と呼ぶ。以下では, 一方向性関数と言っていても実は一方向性関数族のこともある。

3.2 一方向性落し戸付き関数族 (One-Way Trapdoor Function Family)
一方向性関数族 F の各インデックス i にたいして, fi−1 を多項式時間で逆計算できるアルゴリズムが存在するとき, 関数族 F を 一方向性落し戸付き関数族 ((one-way) trapdoor function family) と呼ぶ。fi−1 を fiの落とし戸 (trapdoor) と呼ぶ。
注釈 3

族でない一方向性関数には落とし戸は存在しない。

注釈 4

RSA 関数は, i = (n, e), fi (x) = xe mod n, f −1 (y) = y d mod n によって定義される一方向性落とし戸関数（置換）族の例になっている。ここで n を n = pq なる, 大きな素数 p, q の積, ϕ(·) をオイラー関数とする。e ≥ 3 を, e ∈ (Z/ϕ(n)Z)× なる整数, d を e−1 ∈ (Z/ϕ(n)Z)× （すなわち de = 1 (mod ϕ(n)) ）なる整数とする。

3

3.3 一方向性関数のハードコア述語 (Hard Core Predicate for One-Way Function)
f が一方向性関数とは，x ∈ f −1 (y) を求めることが難しいと言うことであるが，これは例えば，x のいかなる部分情報も求めることが難しいという意味では無いことは次の例から明らかである：任意の一方向性関数 fから，別の一方向性関数 g を g(x, z) := (f (x), z) で定義する（x, z はビット列）。明らかに，g は一方向性関数であるが，x′ = (x, z) の部分ビット列 z を求めるのは簡単である。入力 x に関する情報の内，f (x) を漏らしていても計算することが難しい一ビット b(x) を f (x) のハードコア (hard core) という。以下，もう少し厳密に定義する。
関数 b : {0, 1}∗ → {0, 1} を考える。関数 f, b に対する t(n)-時間アルゴリズム D の成功確率を

()
Advhc
D,f,b (n) := DistD (f (Un ), b(Un )), (f (Un ), U1 )= | Pr [D((f (Un ), b(Un ))) = 1] −D,UnPr

D,Un ,U1[D((f (Un ), U1 )) = 1]|と定義する。ここで，Un , U1 はそれぞれ {0, 1}n , {0, 1} 上の一様分布に従う独立な確率変数である。

Xn := (f (Un ), b(Un ))，Yn := (f (Un ), U1 ) によって確率変数族 X = (Xn )n>0 ，Y = (Yn )n>0 を定義する。
X ≈(t,ϵ) Y の時，関数 b を，関数 f の (t(n), ϵ(n))-ハードコア（又は，(t(n), ϵ(n))-HC ）と呼ぶ。X ≈c Yのとき（すなわち, いかなる PPT アルゴリズム D を考えても, ϵ が無視できる関数になる）, 関数 b を f のハードコア述語 (hard core predicate) と呼ぶ。
任意の一方向性関数から、新たな一方向性関数とそのハードコア述語を作り出せることが知られている。
■Goldreich-Levin の構成 [GL89] 一方向性関数 f に対して、関数 g : {0, 1}∗ → {0, 1}∗ を g(x, r) := (f (x), r)′と定義する。ただし g の入力 (x, r) ∈ {0, 1}n に対して、n′ = 2n のとき、x, r ∈ {0, 1}n 。一方、n′ = 2n + 1のとき, x ∈ {0, 1}n ，r ∈ {0, 1}n+1 とする。さらに関数 b : {0, 1}∗ → {0, 1} を b(x, r) := ⟨x, y⟩ =∑xi · ri mod 2 により定義する。ここで xi はビット列 x の i 番目のビットを意味する。ただし n′ = 2n + 1のときは, xn+1 = 0 と定義する。
この時，次の定理が成り立つ。
定理 5（Goldreich-Levin [GL89]） 任意の一方向性関数 f に対して，上記のように関数 g を定義する。この時
関数 b : {0, 1}∗ → {0, 1} は，g のハードコアである。
注釈 6

Goldreich-Levin の定理の証明のキモは, Hadamard 符号 (Walsh-Hadamard 符号) が local list-decodable 符号であることを示すことと同じである。
■他の構成法 他の構成法として，例えば，素因数分解の困難性を仮定した構成法，離散対数問題の困難性を仮定した構成法などが知られている。

4 擬似乱数生成器 (Pseudo Random Generator)■擬似乱数生成器の定義

大まかに言うと，擬似乱数生成器とは，短い乱数列をその乱数列より長い（一見）ランダムな乱数列に伸ばす確定的アルゴリズムのことである。
任意の n ビット入力を (n + l) ビット列に伸長する（n の多項式時間制限の）確定的アルゴリズム（又は関数）G : {0, 1}∗ → {0, 1}∗ を考える。入力を n ビットに制限すると，G は、G : {0, 1}n → {0, 1}n+l となる。

4この G に対する t(n)-時間確率的アルゴリズム（族）D の識別成功確率を()Advprg
(n)
:=
Dist
G(U),
U
D
nn+lD,G= | Pr [D(G(Un )) = 1] −D,UnPr [D(Un+l ) = 1]|

D,Un+lと定義する。
確率変数族 (G(Un ))n>0 が (Un+l )n>0 から (t(n), ϵ(n))-識別不可の時、G を (t(n), ϵ(n))-擬似乱数生成器（又は、(t(n), ϵ(n))-PRG）と呼ぶ。
c

特に (G(Un ))n>0 が (Un+l )n>0 から計算量的識別不可の時（すなわち (G(Un ))n>0 ≈ (Un+l )n>0 ）、G を擬
似乱数生成器、確率変数 G(Un ) を擬似乱数と呼ぶ。

4.1 擬似乱数生成器の伸長定理
固定された n に対して，G(l) : {0, 1}n → {0, 1}n+l で自然に定義される関数 G(l) : {0, 1}∗ → {0, 1}∗ を nビット列を (n + l)-ビット列に伸長する擬似乱数生成器とする。l を擬似乱数生成器の伸長度と呼ぶ。擬似乱数生成器の伸長度 l := l(n) が n の多項式制限である限り二つの異なる伸長度を持つ擬似乱数生成器に本質的な違いは無い。
■擬似乱数生成器の伸長G(1) を上記の記法に従って伸長度 1 の擬似乱数生成器とする。（入力 n を固定して）関数 G(l) : {0, 1}n → {0, 1}n+l を次のように再帰的に定義する。

G(l) (x) :=()
G(1) (x)[1] || G(l−1) G(1) (x)[2, . . . , n + 1] .

ここで，ビット列 x に対して x[i] は x の i 番目のビットを，x[i, . . . , j] は x の i から j ビット目までのビット列を意味する。上記 G(l(n)) は下記のようにも書き表せる。

G(l(n)) (x) = σ1 · · · σl(n) xl(n) .
ただし、x0 := x, σi := G(1) (xi−1 )[1], xi := G(1) (xi−1 )[2, . . . , n + 1] である。

G(1) が擬似乱数生成器である時，l(n) が多項式制限であるならば，G(l(n)) も擬似乱数生成器であり，以下の定理が成立する。
定理 7

G(1) を (t(n), ϵ(n))-擬似乱数生成器とする。すると、上記の方法で構成された G(l(n)) は (t′ (n), ϵ′ (n))-

擬似乱数生成器であり、t′ (n) ≤ t(n) − (l(n) − 1)TG (n) − TR (l(n) − 1),ϵ′ (n) ≤ l(n) · ϵ(n).
を満足する。ただし、G(1) : {0, 1}n → {0, 1}n+1 を TG (n)-時間確定アルゴリズム、n ビットの乱数列の生成時間を TR (n) で表す。

(証明)
■証明の概要G(l(n)) に対する t′ -時間識別アルゴリズム D′ を考える。次に、D′ をオラクルに使う G(1) に対する識別アルゴリズムを考える。G(1) に対する t-時間識別アルゴリズムの識別確率は仮定により ϵ が上限であるから、結局 D ′ の識別アルゴリズムの上限を抑えることができる。

5

■ハイブリットアーギュメント Xi (0 ≤ i ≤ l) を，{0, 1}n+l(n) 上に値を取る，Xi = Ul−i ||G(i) (Un ) と定義する確率変数とする（但し，G(0) (Un ) = Un ）。

pi := Pr[D′ (Xi ) = 1]′
D ,Xiと定義する。特に X0 = Ul(n) || Un ，Xl = G(l(n)) (Un ) であるので、定義よりAdvprg(n) = |p0 − pl(n) |D ′ ,G(l)である。三角不等式から|p0 − pl(n) | ≤l(n)∑|pi−1 − pi |i=1であることに注意する。次に、|pi−1 − pi | の確率の上限を抑えるため、次のような G(1) の識別アルゴリズム

S i を考える。
■G(1) の識別アルゴリズム S i

S i は n + 1 ビット列 u ∈ {0, 1}n+1 を入力としてとる（u は、一様ランダムな n + 1 ビット列、または G(1) の出力である）。

[アルゴリズム S i ]:1. (l(n) − i)-ビットの一様ランダムな乱数列 r ∈ {0, 1}l(n)−i を選ぶ。
2. ビット列 α := r || u[1] || G(i−1) (u[2, . . . , n + 1]) を作る（u = u[1] || u[2, . . . , n + 1]）。
3. G(l(n)) に対する識別器 D′ にビット列 α を入力する（α が (n + l(n))-ビット列であることに注意）。
4. D′ (α) の出力 b を S i の出力として出力する。
■識別確率の解析 S i は、G(1) に対する識別器であるのでAdvprg(n) = | Pr [S i (Un+1 ) = 1] − Pr[S i (G(1) (Un )) = 1]|.
S i ,G(1)UnUn+1

ここで、()
G(1) (x)[1] || G(i−1) G(1) (x)[2, . . . , n + 1]

G(i) (x) =に注目すると、u が (n + 1)-ビットの乱数列の時は α = Xi−1 であり、一方 u = G(1) (x) (x は n-ビットの乱数列) の時は α = Xi である。よって、

pi−1 = Pr[S i (Un+1 ) = 1],

pi = Pr[S i (G(1) (Un )) = 1]prgが成り立つので、AdvS i ,G(1) (n) = |pi−1 − pi |。

S i の走行時間を t で制限すると、擬似乱数生成器 G(1) の仮定から、Advprg(n) = |pi−1 − pi | ≤ ϵ(n)S i ,G(1)となる。S i の走行時間を t に制限するには、(l − i)-ビット乱数列 r、D ′ の走行時間 t′ 、G(i−1) の実行時間(i − 1)TG (n) から、t(n) ≥ t′ (n) + (l(n) − i)TG (n) + TR (l(n) − i)であればよい。S 1 , . . . , S l の全ての制限時間を t で抑えるには、

t(n) ≥ t′ (n) + (l(n) − 1)TG (n) + TR (l(n) − 1)6とすればよい。このとき、S 1 , . . . , S l の識別確率は全て ϵ で抑えられるから、(n) ≤ l(n) · ϵ(n)Advprg
S i ,G(1)が成り立つ。よって、G(l) の識別器 D ′ は、走行時間がt′ (n) ≤ t(n) − (l(n) − 1)TG (n) − TR (l(n) − 1)のとき、識別確率はϵ′ (n) ≤ l(n) · ϵ(n)で抑えられることが示された。

f : {0, 1}n → {0, 1}n を一方向性置換とする。その時、系8G(l) (x) := f (l) (x) || b(x) || b(f (x)) || · · · · · · || b(f (l−1) (x))
が擬似乱数生成器である。ただし、f (i+1) (x) := f (f (i) (x)) と定義する（f (1) (x) = f (x)）
。

(ヒ ン ト ）定 理 7 と 同 様 に 証 明 で き る 。ハ イ ブ リ ッ ド ア ー ギ ュ メ ン ト が う ま く 構 成 で き る よ う な
乱 数 列 を 探 し て く れ ば よ い 。X0 , . . . , Xl ∈ {0, 1}n を 一 様 分 布 に 従 う 独 立 な 確 率 変 数 と し 、確 率 変数 Y0 , . . . , Yl ∈ {0, 1}n+l を Y0 := X0 || Ul , Y1 := f (X1 ) || Ul′ , Y2 := f (2) (X2 ) || Ul−1 || b(X2 ), . . .,Yl := f (l) (Xl ) || b(Xl ) || · · · || b(f (l−1) (Xl )) と定義する。すると、特にYi =f (i) (Xi ) ||Ul−i−1 ||U1 ||b(Xi ) ||. . . . . . ||b(f (i−1) (Xi ))Yi+1 =f (i+1) (Xi+1 ) ||′Ul−i−1||b(Xi+1 )||b(f (Xi+1 ))||

. . . . . . ||b(f (i) (Xi+1 )).

u ∈ {0, 1}n+1 を、一様ランダムな n + 1-ビット列（u = Un+1 ）、または、f (Un )||b(Un ) とする。α :=u[1, . . . , n] ∈ {0, 1}n , β := u[n + 1] ∈ {0, 1} とすると、
Z := f (i) (α) || Ul−i−1 || β || b(f (α)) || . . . . . . || b(f (i−1) (α)).と置いてやる。u = Un+1 なら、Z = Yi 。一方、 u = f (Un )||b(Un ) なら Z = Yi+1 であることに注意せよ。
問題 9

上記補題を証明せよ。

4.2 一方向性関数 ↔ 擬似乱数生成器■一方向性関数 → 擬似乱数生成器

関数 f が長さ保存で無い場合，構成法は大変非効率な上，証明はとても面倒であるので今回は省略する。一方，関数 f が長さ保存の一方向性置換の時は，構成法はほぼ自明である：f に対するハードコアを b とする。その時，f (x) の最後にハードコアビット b(x) を追加してやれば，この f (x)b(x) は擬似乱数である。
定理 10関数 b を長さ保存の一方向性置換 f に対する (t, ϵ)-ハードコアとする。その時，G(x) := f (x)||b(x)は 1 ビット伸長の (t, ϵ)-擬似乱数生成器である。
問題 11

上記定理を証明せよ。

7

■擬似乱数生成器 → 一方向性関数
定理 12

G : {0, 1}n → {0, 1}n+l が (t, ϵ)-擬似乱数生成器とする。すると、G は、(t, 1−2ϵ −l )-一方向性関数である。

(証明) (ヒント）G の一方向性を破る敵を A とする。A を使って G に対する識別アルゴリズム D を作ってみる。するとその識別確率は A の成功確率 ϵ′ で表現できる。D の走行時間が t であれば、識別確率は高々 ϵであるので、ϵ′ を ϵ の関数で抑えられる。

参考文献[GL89] Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In 21st
ACM STOC, pages 25–32. ACM Press, May 1989.

8