このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

宣伝

 当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。

 暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

『暗号技術のすべて』宣伝サイト

 興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。

置換と関数

 関数とは、ある変数に依存して決まる値あるいはその対応を表す式のことである。簡単にいうと、何か数値を代入すると、その数値に対応した何らかの数値が出力される数式のことである。

 例えば、y=x+1という関数があった場合、xに3を代入(入力)すれば、yは4になる(出力)。このように入力と出力の関係を示す式のことを関数という。この辺りの話はプログラミングをやってる人ならすでに知っているだろう。数学をやっている人なら、写像といったほうがわかりやすいだろうか

 置換とは、あるものを別のものに置き換えることである。関数の場合は重複を許されるが、置換は重複を許されない。つまり、置換は一対一対応の写像である。

 m個の要素がある集合から、n個の要素がある集合への変換に関数を使うとする。このときの関数となりうる変換の数は、mn個になる。
 一方、n個の要素がある集合から、n個の要素がある集合への変換に置換を使うとする(置換の場合は重複を許さないので、同数への写像でしかありえない)。このときの関数となりうる変換の数は、n!個になる。

 例えば、nビット列(n桁あるという意味)は2n通りある。(0,0,…,0,0),…,(0,1,…,0,1),…,(1,1,…,1,1)の総数が2n通りあるということである。{0,1}nという集合から{0,1}nという集合への関数fを考える。この関数の数は、2n通りから2n通りへの関数なので、次のように計算できる。

\sharp~f~=\(2^n~\)^{2^n}~=~2^{{n~\cdot~2}^n}

 一方、{0,1}nという集合から{0,1}nという集合への置換πを考える。この関数の数は、2n通りから2n通りへの置換なので、次のように計算できる。

\sharp~\pi~=~\(~2^n~\)!

 次の図をじっくり見て、理解しておいて欲しい。特に置換の総数が(2n)!通りあるというところが最初はピンと来ないかもしれない。n個の集合からn個の集合への置換の総数はn!通りあるとすでに説明した。このnのところに2nを代入したと考えればよい。

ランダム置換と擬似ランダム置換

 例えば、次のような選択平文攻撃を考える。敵(無限の能力は持たないが、実は選択平文攻撃以外にももっと色々な攻撃ができる)はENCnまたはPnからランダムに選ばれた置換πに平文miを送り、ci=π(mi)を受け取ることができる。

 このような敵が現実的な時間において、ENCnとPnを識別することが困難であるとき、ENCn長さnの疑似ランダム置換族という。

 もう少しわかりやすく解説してみる。仮に、πがランダム置換から持ってきたものであれば、そのπで暗号化されたものはランダム値である。一方、ENCnからπ'を持ってきたとする。これは上記の定義を満たすPnの部分集合である。このπ'を使ったとしても、敵にとってそのπ'がPnから持ってきたのかENCnから持ってきたのかわからななければ、即ちそれがランダム値に見えてしまえば、πは疑似ランダム置換で、ENCnは疑似ランダム置換族ということである。つまり、敵にランダム値を使っているように思わせることができれば(擬似ランダム値でもランダム値のように思う)、セーフということになる。逆に、ランダムではなくなんらかの偏りがあると敵が判断できてしまったら、ダメということになる。

 疑似ランダム置換を厳密に書くと次のようになる。

[定義]

ランダム関数と疑似ランダム関数

 置換のときと同様にしてランダム置換族と疑似ランダム置換族を定義できる。

[定義]
集合{0,1}nから集合{0,1}nへのすべての関数の集合を、Rn={{0,1}SUP{n}:上のすべての関数}と書き、長さnのランダム関数族と呼ぶ。

[定義]
FnをRnの部分集合とする。任意の敵(無限の能力はない)が、FnとRnを識別することが困難なとき、Fn長さnの疑似ランダム関数族と呼ぶ。

 直観的に考えると、ランダム関数とは与えられた入力に対して、その出力が決定されるものの、その出力はどんな情報からも推測できないランダムな値であるような関数のことである。もっと直観的にいうと、ランダム関数から出力された値は完全なランダム値になっていて、何を入力したかは推測できないということである。

 このような関数が現実に存在するかどうかは別として、そのような関数の振る舞いをブロック暗号の性質に見立ててて、利用モードの安全性を議論したりする。簡単にランダム(乱数)と言葉に出していますが、ランダム値を実現することは実際には非常に困難である。

ユニバーサルハッシュ関数利用による擬似ランダム関数の定義域の拡張

[定義]キー関数の族
l1,l2が与えられた。
F:={Fs}s∈S:キー関数の族

[定義]
F_{s}~:~\bigl\{0,1\bigr\}^{l_{1}}~\to~\bigl\{0,1\bigr\}^{l_{2}}
\Gamma_{l_{1},l_{2}}~:~\bigl\{0,1\bigr\}^{l_{1}}~\to~\bigl\{0,1\bigr\}^{l_{2}}
となる関数の集合

[定義]
「F:擬似ランダム関数」
⇔SUP{def}「オラクルアクセスをして1ビット出力するような\Gamma_{l_{1},l_{2}}の要素となる関数」

[定義]PRF-advantage(擬似ランダム関数の識別利得)
PRF-advantage~\,~(of~\,~A)~:=~|~Pr[s~\overset{$}{\leftarrow}~S~:~A^{F_{s}}()=1]-Pr[f~\overset{$}{\leftarrow}~\Gamma_{l_{1},l_{2}}:A^{f}()=1]|

[定義]擬似ランダム関数
「AのPRF-advがneg」⇒「F:擬似ランダム関数」

 つまり、Fと\Gamma_{l_{1},l_{2}}のどちらが選ばれているかわからないとき、Fは擬似ランダム関数ということである。

[定義]キーハッシュ関数の族
l:整数、l>l1
H:={Hk}k∈K
H_{k}~:~\bigl\{0,1\bigr\}^{l}~\to~\bigl\{0,1\bigr\}^{l_{1}}

[定義]εuh
\forall~w,w'~\in~\bigl\{~0,1~\bigr\}^{l}~,~w~\not=~w'~\,s.t.\,~Pr[k\overset{$}{\leftarrow}K~:~H_{k}(w)=H_{k}(w')];neg
のとき、εuhという。

 Hはハッシュ関数のεuhユニバーサル族と仮定する。

[定義]
関数族F':={F'k,s}(k,s)∈K×S
F'~:~\bigl\{0,1\bigr\}^{l}~\to~\bigl\{0,1\bigr\}^{l_{2}}
F'_{k,s}(w)~=~F_{s}(H_{k}(w))

 ハッシュ関数を使うと大きい定義域を持った擬似ランダム関数を作れる。

F':~\bigl\{0,1\bigr\}^{l}~\underset{H_{k}}{\longrightarrow}~\bigl\{0,1\bigr\}^{l_{1}}~~\underset{F_{s}}{\longrightarrow}~\bigl\{0,1\bigr\}^{l_{2}}

 l>l1だから、最初の擬似ランダム関数から比べて定義域が大きくなったことがわかる。

 その作った関数が本当に擬似ランダム関数かどうかを証明しなければならない。

定義域を拡張した関数は、PRF,UH仮定の下で擬似ランダム関数

[定理]PRF,UHの下で、「F:擬似ランダム関数」⇒「F':擬似ランダム関数」

[方針]次の確率の差の絶対値がnegならば、証明できたことになる。

|Pr[s~\overset{$}{\leftarrow}~S,k~\overset{$}{\leftarrow}~K;~A^{F_{s,k}}()=1]~-~Pr[f~\overset{$}{\leftarrow}~\Gamma_{l_{1},l_{2}};A^{f}()=1]|

 前半の確率がGame0、後半の確率がGame3である。

[証明]∀A:Adversary

[1]Game0

 Aはオラクルに投げているつもり。

S0=defthe event that b=1 in Game0

[2]Game1

S1=defthe event that b=1 in Game1

 DOとは、オラクルOにアクセスできる識別子Dである。

\epsilon_{pcf}(~D^{O}~)~=~|Pr[s~\overset{$}{\leftarrow}~S~,~k~\overset{$}{\to}~K;A^{F_{s,k}}()=1]~-~Pr[f~\overset{$}{\leftarrow}~\Gamma_{l_{1},l_{2}}~,~k~\overset{$}{\leftarrow}~K~;~A^{F_{s,k}}()=1~]|

=|Pr[S_0]-Pr[S_1]|

|Pr[S_0]-Pr[S_1]|=\epsilon_{pcf}~\,~;~\,~neg

[3]Game2

S2=defthe event that b=1 in Game2

 Aはwを投げると、Hを使ってxが計算される。すると、xに対応するyがAに返される。このとき、If Else文にあるように、すでに前に出たxと同じ値なら、巨大なテーブルからyを持ってくる。一方、すでにまだ出ていないxなら、普通にランダムな値を持ってくる。

∴Pr[S1]=Pr[S2]

[4]Game3

S3=defthe event that b=1 in Game3

F:xi=xj(∃i≠∃j)のときのイベント
とする。

「S2∧¬F」⇔「S3∧¬F」より、|Pr[S2]-Pr[S3]|≦Pr[F]が成り立つ。

wi≠wj(i≠j)のとき、
Pr[xi=xj]
=Pr[Hk(wi)=Hk(wj)]
≦Pr[F]
≦εuh×q(q-1)/2 (∵q個あるうち2個取って衝突するパターンはqC2通りある)
≦εuh×q2/2

 よって、|Pr[S2]-Pr[S3]|≦εuh×q2/2

 したがって、

|Pr[S3]-Pr[S0]|
≦|Pr[S3]-Pr[S2]|+|Pr[S2]-Pr[S1]|+|Pr[S1]-Pr[S0]|
prfuh×q2/2 (∵第2番目の絶対値は0)

∴|Pr[S3]-Pr[S0]|;neg (Q.E.D.)

[考察]Fが起きないときのk,r,Y1,…,Yqを考える。

(a)i=0のとき、自明

(b)i=1のとき、成り立つと仮定。
wi,x:同じ方法を決定
Fが起きなければ、yiも同じ
つまり、b=A(r,Y1,…,Yq)は同じ。

擬似ランダム置換⇒擬似ランダム関数

[定義]
l∈N+
S:鍵集合
P_{s}:\bigl\{~0,1~\bigr\}^{l}~\rightarrow~\bigl\{~0,1~\bigr\}^{l}:置換
P~\overset{def}{=}~\bigl\{~P_{s}~\bigr\}_{s~\in~S}

[定義]
\Pi_{l}~\overset{def}{=}~\bigl\{\forall~\pi~:~\bigl\{~0,1~\bigr\}^{l}~\rightarrow~\bigl\{~0,1~\bigr\}~\bigr\}:置換の族
\Gamma_{l,l}~\overset{def}{=}~\bigl\{\forall~f~:~\bigl\{~0,1~\bigr\}^{l}~\rightarrow~\bigl\{~0,1~\bigr\}~\bigr\}:関数の族

P⊂Πl⊂Γl,l

[定義]
∀A(敵)、 PRP-advantage~\,~of~\,~A~\,~for~\,~P\overset{def}{=}~|Pr[s~\overset{$}{\leftarrow}S;A^{P_{s}}()=1]-Pr[\pi\overset{$}{\leftarrow}\Pi_{l};A^{\pi}()=1]|

[定義]
「P:擬似ランダム(pseudo-random)」
def「∀A、(PRP-advantage of A ofr P):neg」

RF vs RP

 「P:PRP族」⇒「P:PRF族」を示したい。

 そこで、まずRF(ランダム関数)とRP(ランダム置換)を識別する問題を考える。

[定義]
∀A(敵)、 RF/RP-advantage~\,~of~\,~A~\,~for~\,~P\overset{def}{=}~|Pr[f~\overset{$}{\leftarrow}\Gamma_{l,l};A^{f}()=1]-Pr[\pi\overset{$}{\leftarrow}\Pi_{l};A^{\pi}()=1]|

[定理]
∀A:少なくともq回オラクルアクセスが可能な敵
(RF/RP-advantage~\,~of~\,~A~\,~for~\,~P)~\le~\frac{q^2}{2}\cdot~2^{-l}

[証明]

∀i,j;i≠j、xi≠xj

[1]Game0

S0=defthe event that b=1 in Game0

[2]Game1

 Aにとっての目的は、置換か普通の関数かを区別したい。そのためには値の衝突を見るしかない。ここで、オラクルが単にランダムにとってきてしまうとどこかでAにばれてしまう。そこで、オラクルはAにばれないようにIf Else文で前に出たランダム値が来たら別のものを取り直すようにしている。

S1=defthe event that b=1 in Game1

Pr[S1]=Pr[S0]

[3]Game2

 オラクルはダイレクトに返しているだけ。

S2=defthe event that b=1 in Game2

 ここで、次のようにFを定義する。

F=defthe event that Yi=Yj for some i≠j

 r,Y1,…,YqはGame1とGame2を同一視できる。つまり、同じランダムテープを使っている。即ち、各ランダムテープの値までもがぴったり一致している。これは、ランダム値の全体の集合が一致するということより強いことがいえているわけだ。

 よって、「S1∧¬F」⇔「S2∧¬F」

∴|Pr[S1]-Pr[S2|≦Pr[F]

 後は、Pr[F]を細かく見ていけばよい。

 イベントFは、q個の要素から2つのペアを取り出して、それが一致していない組み合わせが起こるというのが前提である。これは、q個のボールを同時に2個取り出す組み合わせ、即ちqC2通りあると考えればよい。

Pr[F]
=qC2・2-l
={q(q-1)/2}・2-l
≦{q2/2}・2-l

(RF/RP-advantage~\,~of~\,~A~\,~for~\,~P)~\le~\frac{q^2}{2}\cdot~2^{-l}

PRF vs PRP

[定理]
l:十分大きい s.t. 2-l;negとする。
「P:PRP族」⇒「P:PRF族」

[証明]

 Pに対する効率的なアドバーサリーAをfixして、PRF-advantageがnegであることを示す。

\epsilon_{pcf}~=~|Pr[s~\overset{$}{\leftarrow}~S~,~k~\overset{$}{\leftarrow}~K:A^{F_{s,k}}()=1]~-~Pr[f~\overset{$}{\leftarrow}~\Gamma_{l_{1},l_{2}}~,~k~\overset{$}{\leftarrow}~K~:~A^{F_{s,k}}()=1~]|=|Pr[S_0]-Pr[S_1]|

 このεprfがnegであることを示す。

 まず、仮定より

\epsilon_{prp}~=~|Pr[s~\overset{$}{\leftarrow}~S~,~k~\overset{$}{\leftarrow}~K:A^{F_{s,k}}()=1]~-~Pr[\pi~\overset{$}{\leftarrow}~\Pai_{l}~,~k~\overset{$}{\leftarrow}~K~:~A^{F_{s,k}}()=1~]|=|Pr[S_0]-Pr[S_1]|;neg

 また、RS vs RPの議論より次が成り立つ。

\epsilon_{rf/rp}~\,~\overset{def}{=}~|Pr[f~\overset{$}{\leftarrow}\Gamma_{l,l};A^{f}()=1]-Pr[\pi\overset{$}{\leftarrow}\Pi_{l};A^{\pi}()=1]|~\le~\frac{q^2}{2}\cdot~2^{-l}

 これは、Aにとって、πl、Γl,lから選ばれているかわからないということ。

 よって、

\epsilon_{pcf}

=~|Pr[s~\overset{$}{\leftarrow}~S~,~k~\overset{$}{\leftarrow}~K:A^{F_{s,k}}()=1]~-~Pr[f~\overset{$}{\leftarrow}~\Gamma_{l_{1},l_{2}}~,~k~\overset{$}{\leftarrow}~K~:~A^{F_{s,k}}()=1~]|

\le~~|Pr[s~\overset{$}{\leftarrow}~S~,~k~\overset{$}{\leftarrow}~K:A^{F_{s,k}}()=1]~-~Pr[\pi~\overset{$}{\leftarrow}~\Pi_{l}~,~k~\overset{$}{\leftarrow}~K~:~A^{F_{s,k}}()=1~]|~+~|Pr[f~\overset{$}{\leftarrow}\Gamma_{l,l};A^{f}()=1]-Pr[\pi\overset{$}{\leftarrow}\Pi_{l};A^{\pi}()=1]|

\epsilon_{prp}~+~\epsilon_{rf/rp}

 ゆえに、negで押さえられる。

LRC

[定義]
F:={Fs}s∈S:擬似ランダム関数の族
Fs:{0,1}l→{0,1}l

[定義]
H:={Hk}k∈K:lビット長のハッシュ関数のεaxu-almost-XOR-universal族
Hk:{0,1}l→{0,1}lとする。

\forall~x,x',y~\in~\bigl\{~0,1~\bigr\}^l~(x~\not=~x')~;~Pr[k~\overset{$}{\leftarrow}~K~;~H_{k}(x)~\oplus~H_{k}(x')=y]~\le~\epsilon_{axu}

 ここで、εaxuはnegと仮定する。

[定義]Luby-Rackoff Construction(LRC)

LRC⇒PRP

[定理]LRC⇒PRP

[方針]
「LRC⇒PRF」(示したいもの)
「PRF⇒PRP」(ここで証明済み)
を使う。

[証明]

[1]Game0

S0=defthe event that b=1 in Game0

[2]Game1

S1=defthe event that b=1 in Game1

|Pr[S0-Pr[S1|=εprf

 オラクルマシンDOを次のように設定する。

[3]Game2

S2=defthe event that b=1 in Game2

|Pr[S1-Pr[S2|=ε'prf

 オラクルマシンD'Oを次のように設定する。

 さらに、オラクルマシン~DOを次のように設定する。

「|Pr[S1-Pr[S2|=ε'prf;neg」を証明する。

F_s:\bigl\{~0,1~\bigr\}^{l}~\to~\bigl\{~0,1~\bigr\}^{l}

\Gamma_{l,l}:\bigl\{~0,1~\bigr\}^{l}~\to~\bigl\{~0,1~\bigr\}^{l}

|Pr[s~\overset{$}{\leftarrow}~S;\tilde{D}^{F_{s}}()=1]~-~Pr[f~\overset{$}{\leftarrow}~\Gamma_{l,l};\tilde{D}^{f}()=1]| ←(*)

ここで、Pr[\tilde{D}^{F_{s}}()=1]

=\frac{1}{2}~Pr[{D}^{F_{s}}()=1]~+~\frac{1}{2}~Pr[{D'}^{F_{s}}()=1]

=\frac{1}{2}~Pr[S_{0}]~+~\frac{1}{2}~Pr[S_{1}]

また、Pr[\tilde{D}^{f}()=1]

=\frac{1}{2}~Pr[{D}^{f}()=1]~+~\frac{1}{2}~Pr[{D'}^{f}()=1]

=\frac{1}{2}~Pr[S_{1}]~+~\frac{1}{2}~Pr[S_{2}]

∴(*)=~|~\frac{1}{2}~Pr[S_{0}]~-~\frac{1}{2}~Pr[S_{2}]|

=\frac{1}{2}~|Pr[S_{1}]~-~Pr[S_{2}]|

[4]Game3

S3=defthe event that b=1 in Game3

F_1:w_i~=~w_j~\,~(i~\not{=}~j)

F_2:x_i~=~x_j~\,~(i~\not{=}~j)という2つのイベントを考える。

F=F1∨F2より、Pr[F]~=~Pr[F_1]~+~Pr[F_2| ←(1)

また、「「S2∧F」⇔「S3∧F」」より、|Pr[S_{2}]~-~Pr[S_{3}]|~\le~Pr[F] ←(2)

ここで、

Pr[F_2]~=~Pr[x_i~=~x_j]=\frac{q(q-1)}{2}\cdot~\frac{1}{2^l}~\le~\frac{q^2}{2}\cdot2^{-l}

∵まずlビットだからl列の0…0〜1…1を考える。

その総数は2l通りある。つまり、最初にxiを決定する確率は1/2lとなる。

その確率で、繰り返し数qからひとつ選択する。

また、xjはひとつ減らしたq-1からひとつ選択することになる。

結局合計で、q×(q-1)×2lとなる。

q個から2個自由な組合わせで取り出す(重複はなし)総数はqC2通りある。このようにコンビネーションで考えてもよい。

Pr[F_1]~=~Pr[w_i~=~w_j]

=~Pr[u_i~\oplus~H_{k}(v_i)~=~u_j~\oplus~H_{k}(v_j)]

=~Pr[H_{k}(v_i)~\oplus~H_{k}(v_j)=u_i~\oplus~u_j] (XOR演算は移行できる)

=~Pr[(H_{k}(v_i)~\oplus~H_{k}(v_j)=u_i~\oplus~u_j~)~\wedge~~(~v_i=v_j~)]~+~Pr[(H_{k}(v_i)~\oplus~H_{k}(v_j)=u_i~\oplus~u_j~)~\wedge~(~v_i~\not{=}~v_j~)]

\le~0~+~\frac{q^2}{2}\cdot~\epsilon_{axu}

∵vi=vjのとき、ui≠uj、つまり、wi≠wj よって、確率0

また、vi≠vjのとき、u_i~\oplus~u_j~\in~\bigl\{~0,1~\bigr\}^{l}

 ゆえに、

|Pr[S_{0}]~-~Pr[S_{3}]|

\le~|Pr[S_{0}]~-~Pr[S_{1}]|~+~|Pr[S_{1}]~-~Pr[S_{2}]|~+~|Pr[S_{2}]~-~Pr[S_{3}]|

\le~|Pr[S_{0}]~-~Pr[S_{1}]|~+~|Pr[S_{1}]~-~Pr[S_{2}]|~+~Pr[F]

=~\epsilon_{prf}~+~\epsilon_{prf'}~+~\frac{q^2}{2}(\epsilon_{axu}~+~2^{-l})

 よって、neg (Q.E.D.)

参考文献

  • ゼミノート
  • 『現代暗号の基礎数理』
  • 論文「Seqences of Games:A Tool for Taming Complexity in Security Proofs」