6-43 量子アルゴリズムを用いたディジタル暗号化方式の安全性評価 桑門秀典 神戸大学大学院工学研究科准教授 はじめに 現在の電気通信は ディジタル情報伝送とディジタル情報処理によって支えられている. 一方で 量子情報を伝送 処理する量子通信や量子情報処理の研究が活発に行われており 将来の通信技術として期待されている. しかし ディジタル情報と量子情報は その基本的な性質の違いから 排他的なものではない. したがって 量子情報処理が実用化されたとしても 現在のディジタル情報にすぐに取って代わるとは考えにくく 両者が共存する時期が長く続くと考えられる. 量子計算機はまだ実現していないが 量子素子の研究開発が盛んに行われているので 現在の共通鍵ブロック暗号とハッシュ関数が使用されているうちに実現する可能性も否定できない. したがって ディジタル情報を処理するハッシュ関数や共通鍵暗号の安全性を量子アルゴリズムで評価することには 意義がある. 量子アルゴリズムに対して ハッシュ関数や共通鍵暗号が原理的に越えることができない安全性の限界があることを示した先行研究があるが これは 適切に設計すれば 量子コンピュータが実現した場合でも 高い安全性を実現できることも示唆している [3][4]. しかしながら 先行研究は ハッシュ関数や共通鍵暗号を完全にブラックボックスとして扱っていること 事前に与えられる仮定が現在のハッシュ関数にあわないこと など現実にそぐわない部分があった. 本研究の動機は この現実に合わない部分を改善し 現在のハッシュ関数や共通鍵暗号がどの程度限界に近いのかを明らかにすることである. 本研究では ハッシュ関数や共通鍵暗号が小さいプリミティブの繰り返し構造になっている点に着目する. 理論的な安全性解析を行う場合 そのプリミティブが理想的であることを仮定し ハッシュ関数や共通鍵暗号全体が安全であることを示す方法が一般的である. したがって プリミティブが理想的であるかどうか つまり プリミティブが理想とされているものから識別可能かどうかという点が非常に重要である. そのような識別可能性を議論する際に ランダム置換とランダム関数の識別可能性が重要な役割を果たすことがこれまでの古典暗号の安全性の議論から分かっている. そこで 本研究では 量子アルゴリズムを用いて ランダム置換とランダム関数の識別可能性の検討を行う - RP/RF 識別問題 l F を :{ } { } の全ての関数の集合とする. l からランダムに選ばれた関数をランダム l F 関数 (radom uctio: RF) と呼ぶ. P を p :{ } { } の全ての置換の集合とする. からラ P ンダムに選ばれた置換をランダム置換 (radom permutatio: RP) と呼ぶ. g を P のランダム置換または F のランダム関数のオラクルとし g がランダム置換なのか ランダム関数なのか を決定する問題を RP/RF 識別問題と呼ぶ. g へオラクルアクセスを q 回行い または を出力するアルゴリズム A を考え る. アルゴリズム A がそれらを識別する能力を評価するために A の rpr-advatage を以下のように定 古典暗号の安全性の解析を行う場合は ランダム置換とランダム関数ではなく 擬似ランダム置換 (pseudoradom permutatio: PRP) と擬似ランダム関数 (pseudoradom uctio: PRF) の識別困難さについて議論する場合が多い. したがって RP/RF ではなく PRP/PRF という言葉が用いられる. 計算量的な仮定である擬似ランダム関数 擬似ランダム置換の方が 理想的な仮定であるランダム関数 ランダム置換よりも現実の古典暗号のモデル化として妥当である. 35
義する. g g ( A) = Pr g F ; A Pr g P ; A rpr Adv q この rpr-advatage が大きいほど アルゴリズム A の識別能力が高いことを意味する. なお A の出力は または なので A は g がランダム関数である証拠 あるは g がランダム置換である証拠を出力する必要はないことに注意しよう. A が古典アルゴリズムであり A は古典オラクル g へ q 回のオラクルアクセスをする ( クエリをする ) と 仮定する. このとき A の rpr-advatage は rpr qq ( ) Adv q ( A) + である [5]. A が古典的であることとクエリ回数が q 回であること以外 A の計算能力については何ら 制限をしていないので いかなる古典アルゴリズム A も RP/RF 識別問題に有意な解を出力するためには O ( / ) 回のオラクルアクセスが必要である. 本研究では RP/RF 識別問題において ランダム関数を r 対 関数に限定した場合を考察する. ここで r 対 関数とは つの写像に対して原像が常に r 個あるような関数である. つまり 任意の x { } l の y = ( x) に対して r l r = #{x y = ( x) x { } l }. l F を :{ } { } への全ての r 対 関数の集合とする. r F l からランダムに選ばれた r 対 関 数を r 対 ランダム関数という. r = の場合は 対 ランダム関数はランダム置換なので 以後 r とする. g を F の r 対 ランダム関数または のランダム置換のオラクルとし g が r 対 ランダム r P 関数なのか ランダム置換なのかを決定する問題を RP/ r -RF 識別問題と呼ぶことにする. アルゴリズム A の RP/ r -RF 識別能力を評価するために A の rprr-advatage を以下のように定義する. r g g ( A) = Pr g F ; A Pr g P ; A rprr Adv q 本研究では A が量子アルゴリズムであり g の計算を行う量子回路にオラクルアクセスする場合 RP/ r -RF 識別問題の rprr-advatage を評価する. 従来方式との関係 - Deutsch のアルゴリズム Deutsch の問題は 関数値の排他的論理和を計算する問題である. この問題が RP/RF 識別問題の特殊な場合であることを後で説明する. 36
Deutsch の問題 -bit の関数 :{ } { } がオラクルとして与えられる. () () の値を求めよ. -bit の関数 :{ } { } がオラクルとして与えられる. () () の値を求めよ. Deutsch のアルゴリズムは を計算するオラクルを量子回路の場合 回のクエリ ( オラクル呼出 ) で () () の値を決定できる. 具体的なアルゴリズムは下記のとおり. を計算する uitary operator をU とする. x > と y> を とする. U の出力は U : x> y> x> ( x) y> x > = > + > y> = > > U > + > > > = U > ( > > ) + > ( > > ) ( ) = ( () () ) + ( () () ) ( > > > > > > ) = ( > ( () > () > ) + > ( () > () > ) ) () となる. ここで () () { } なので 下記の等式が成立するので () () > () > > () > = ( ) > > ( ) > > () () > () > > () > = ( ) > > ( ) > > 式 () に代入すると ( ) ( ) () () () U > + > > > = ( ) > + ( ) > > > 最初のキュービットを双対基底で測定すると アダマール変換を H として ( () > i () () = H () > + ( ) > ) = > i () () = となるので その測定結果で () () の値が判明する. この量子アルゴリズムは確定的であり 必 ず正しい値が得られることに注意しよう. Deutsch の問題が この研究の対象となっている RP/RF 識別問題の特殊な場合であることを説明しよう. 37
bit から bit への関数全ての集合 F は ここで 関数 i は以下のとおり. bit から bit への置換全ての集合 P は ここで 置換 P 定義から pi は以下のとおり. F = { 3 } () = () = () = 3() = () = () = () = 3() = P = {p p } p () = p () = p() = p () = F なので F P = { 3 } からランダムに選ばれた関数 と P = {p p } から ランダムに選ばれた関数 p の識別問題になる. さらに F P は F なので RP/-RF 識別問題であ る. 関数 は () () = 置換 p は p() p() = となっているので と p の識別問題は Deutsch の問題に帰着する. 故に bit 入出力の RP/-RF 識別問題は 量子アルゴリズムを用いることで任意の古典アルゴリズムよりも少ないオラクル呼出で 誤ることなく常に識別可能である. - Simmos のアルゴリズム Simmos は 置換と特殊な関数の識別問題 (Simmos の問題 ) を考え この問題が多項式時間の量子アルゴリズムで解けるが 多項式時間の古典アルゴリズムでは解けないことを示した. Simmos の問題と RP/RF 識別問題の違いについては 後で説明する. Simmos の問題 :{ } { } がある. この は 下記のいずれかの性質を満たす.. 置換である.. 対 であり かつ異なる任意の ab { } に対して ( a) = ( b) b= a s 3. となる s が一つ存在する. がどちらの条件を満たすかを決定せよ. もし 対 の場合 s も求めよ. この問題を解く確率的量子アルゴリズムを示す. を計算する uitary operator をU とする. 初期 状態 > の左側の キュービットにアダマール変換を適用して ϕ = x >. x { } 38
を作成する. ϕ にU を適用して を得る. x > にアダマール変換を適用して 3 ϕ = U x > x { } = x ( x ) >. x { } xy ϕ = ( ) y ( x ) >. () x { } y { } を得る. そして ϕ 3 を観測して ( y ( x)) を得る. これをl 回繰り返して ( y ( x )) ( y ( x)) ( y ( x )) を得る. が置換の場合 式 () は 通りの全ての状態が等しい振幅で重ね合わさって l l いるので 観測結果 ( y ( x )) はその中からランダムに選ばれた状態である. 一方 が 対 の場合 i i 式 () において y ( x ) > と y ( x s ) > は同じ状態になるので 置換の場合とは異なり 通り の全ての状態が等しい振幅で重ね合わさっているのではない. y ( x ) > と y ( x s ) > の振幅は xy ( x s) y ( ) / と ( ) / であるから ( ) i mod ( ) xy ( ) x s y y s = + = i y s = mod ここで y s は y と s を其々 元の 次元ベクトルとみなしたときの内積を表す. したがって 観測 して得られた ( yi ( xi)) の y i は を満たす. いずれの場合も l 個の yi s = mod (3) y i が入手できているので y s = mod y s = mod yl s = mod なる連立方程式をたてることができる. l が よりも十分に大きいと仮定する. もし が置換であるな らば y i はランダムな値なので この連立方程式を満たす s は存在しない. 一方 もし が 対 なら 39
ば 式 (3) よりこの連立方程式を満たす s は一意に求まる. なお l が よりも十分に大きいという仮定 から y i を 次元の 元ベクトルとみなすと y y y l の中に線形独立なベクトルが 個以上あるこ とを期待している. しかし 線形独立なベクトルが必ず 個以上あることは保証できないので 上記のアルゴリズムは確率的 つまり必ずしも成功は保証されない点が Deutsch の問題のアルゴリズムとは異なる. Simmos の問題における 対 関数には制約があるため 対 ランダム関数ではない. しかし ( a) = ( b) となる ab に線形関係がある場合には 量子アルゴリズムが古典アルゴリズムよりも効率良 くランダム置換と識別できることを示している. なお 古典アルゴリズムで Simmos の問題を解くためには指数関数時間を要することがヤオの最小化原理から導かれる. -3 Brassard らのアルゴリズム Brassard らは r 対 関数 が与えられたとき ( x) = ( x) となる x x を計算する量子アルゴリ ズムを示した (BHT アルゴリズム )[3]. ランダム置換 p には p( x) = p( x) となる x x は存在しないので BHT アルゴリズムを利用して RP/ r -RF 識別問題を解くアルゴリズムが構成できる. まず BHT アルゴリズムの述べよう. g を F の r 対 ランダム関数とする. { } からt = ( / r ) / 個の相異なる要素をランダムに選び その集合を X とする. 各 i r X = {x x x } x { } t i x に対して yi = g( xi) を ( 古典的に ) 計算し y i の値に従って整列した ( x j y j) の ( 古典的な ) 表 T を 作成する. 次に 以下のような関数 v :{ } { } を計算する uitary operator Uv が与えられた 3 とする. i x / X ( xj g( x)) T or xj vx ( ) = otherwise. このとき U を用いて Grover アルゴリズム [4] を実行して 出力 w を得る. そして 表 T の中から v ( x gw ( )) となる項を探索する. もし発見できれば ( x w) を出力し 発見できなければ 発見できな k かったをことを示す を出力する. Grover アルゴリズムの出力 w は高い確率で vw ( ) = となるが vw ( ) = な w を出力する可能性もある ので その意味で BHT アルゴリズムは確率的である. BHT アルゴリズムの計算量を古典的な部分と量子的な部分に分けて評価する. 古典的な部分は 表の作成 整列 探索である. 作成には Ot () 整列には Ot (log) t 探索には O(log t) の計算量が必要である. なお 作成の計算量はクエリ回数であるが 整列 と探索はそうではないことに注意しよう. 量子的な部分は Grover アルゴリズムであり k Uv へのクエリ 回数は O( / t) である. t r / 3 = ( / ) なので r が に対して十分に小さい定数と仮定すると 古典 3 的にO ( / 3 ) 量子的にO ( / ) となる. 古典アルゴリズムのみで gx ( ) = gx ( ) となる x x を求めるため 3
には O ( / ) のクエリ回数が必要であるから 量子アルゴリズムを用いることで 計算量が大幅に削減 することができる. g がランダム置換の場合 BHT アルゴリズムの動作を考えよう. vw ( ) = になるような w { } が存 在しないので Grover アルゴリズムは { } からランダムに選ばれた要素を w として出力する. した がって 表 T の中から ( xk gw ( )) なる項目を探索しても存在しない場合がある. 存在した場合 x k ある. = w で BHT アルゴリズムをサブルーチンとする g に関する RP/ r -RF 識別問題に対するアルゴリズム A を以下 のように構成できる.. g に対して BHT アルゴリズムを実行し その出力を得る.. 出力 ( x w) が得られた場合 : k もし gx ( k ) = gw ( ) かつ x k もし gx ( k ) gw ( ) または x k w の場合 を出力する. = w の場合 を出力する. 3. 出力 が得られた場合 : を出力する. Grover アルゴリズムの出力 w が vw ( ) = となる確率を P ( q) とおく. ここで q はU へのクエリ回数 である. A の rprr-advatage を評価すると G v なので r g g Pr g F ; A = PG( q) Pr g P ; A = rprr Adv q ( A) = P ( q) G 3 となる. Grover アルゴリズムの性質から q= O ( / ) で P ( q) となる. したがって BHT アルゴ リズムをサブルーチンとして用いれば RP/ r -RF 識別問題は / 3 程度のクエリで識別可能である. 古典 アルゴリズムでは / 程度のクエリが必要なので クエリ回数が大幅に削減されている. G -4 考察 RP/ r -RF 識別問題の特殊な例となる Deutsch の問題や Simmos の問題では クエリ回数の点で量子アルゴリズムが古典アルゴリズムよりも優れていることを示した. 古典アルゴリズムでは取り得る値が複数あった場合 それらが排他的であるのに対し 量子アルゴリズムでは取り得る値がアダマール変換等により 重ね合わされているので つまり関数 全体の様相を作っているので 関数全体の性質を効率良く決定で きている. 一般的な RP/ r -RF 識別問題においても 量子アルゴリズムが古典アルゴリズムより効率が良いことを示した. しかし BHT アルゴリズムを利用したアルゴリズムでは 識別問題が要求していない 証拠 ( 具体的には ランダム関数の場合の衝突する入力の組 ) まで求めている. この余計な計算を省略できれば 効率をさらに改善できる可能性がある. 古典暗号の安全性の概念の一つに 識別不可能性の概念がある. これは 理想とする関数を最初に決め 3
実際に構成した関数がその理想とする関数と識別できる確率を評価することで 構成した関数の安全性を示すものである. 例えば 共通鍵暗号では 鍵が未知のとき暗号化関数はランダム置換と識別不可能であることを設計目標とする. また ハッシュ関数では ランダム関数と識別不可能であることを設計目標とする. 前節までで示したしたように 識別不可能性を議論するときには 古典アルゴリズムより量子アルゴリズムが強力な場合がある. したがって 古典暗号の識別不可能性を量子アルゴリズムで評価することは意味がある. 3 RP/-RF 識別問題 本研究では まず RP/-RF 識別問題について議論する. RP/-RF 識別問題を具体的に述べると 下記のようになる. RP/-RF 識別問題は Simmos の問題と似ているが Simmos の問題のような線形はないことに注意しよう. また = のときは Deutsch の問題とほぼ等価である (. 節参照 ). RP/-RF 識別問題 g :{ } { } がある. この g は 下記のいずれかの性質を満たす. 4. g はランダム置換である. 5. g は 対 ランダム関数である. g がどちらの条件を満たすかを決定せよ. 3- クエリ回数が 回の場合クエリ回数が 回の場合の RP/-RF 識別問題を考える. 古典アルゴリズムの場合 いかなる古典アルゴ リズム A も g を識別できない. つまり Adv rp r ( A) =. 次に 量子アルゴリズムの場合を考えよう. g の計算を行う uitary operator をU とする. 回用いて g の性質を推定する量子アルゴリズム A を述べる.. 下記のような状態 ϕ > を用意する.. U g を作用させて ϕ > = x> > x { } g U g を ϕ > = U ϕ > g = x >g ( x ) > x { } 第二レジスタの gx> ( ) の部分を測定する. 測定後 この部分は固定されるので 以後この部分の記述を 省略する. 測定後の状態は g の性質によって異なる. 3
x > i g is RP ϕ3 > = x > + x > i g is RF. 3. H を ここで x i 行 列のアダマール行列とする. ϕ > 3 に H を作用させると ϕ > = H ϕ > 4 3 x z ( ) z> i gisrp z { } = x z x z ( ) + ( ) z> i gis RF + z { } z は xi = xi xi x i > z = z z > としたとき x z x z = i i j j j= mod である. 4. ϕ > 4 を測定する. もし が測定されれば を出力し それ以外であれば を出力する Step 4 の測定において g がランダム置換の場合 が測定される確率は/ である. 一方 g が 対 ランダム関数の場合 が測定される確率は/ である. したがって となり g g Pr g F ; A = Pr g P ; A = Adv ( A) = rpr rpr である. 古典アルゴリズムの場合 いかなるアルゴリズムでも Adv ( A) = なので 量子アルゴリ ズムの方が優れていることがわかる. 特に が小さい場合には ( 例えば = 3 ) 上記の量子アルゴ リズムの rpr-advatage は 無視できない値である. 3- クエリ回数が q 回の場合前節で述べたアルゴリズムは ビット数 が小さい場合には有効であるが が大きくなると 漸近的 に rpr-advatage が になるアルゴリズムであった. 本節では が大きく クエリ回数 q が多い場合に 有効なアルゴリズムを示す.. クエリ回数をカウントするためのカウンタ c q 測定結果の累計をカウントするためのカウンタ c c. cq を に初期化する. = qならば Step に行く. そうでなければ c q の値を 増やす. 33
3. 状態 > を用意する. > = > > >. 4. 第一レジスタと第三レジスタに Hadamard 変換を施す. > = ( H I H ) > > + > = x> > x { } ここで H と I は それぞれ Hadamard 行列と 単位行列である. ψ 5. Ug I を > に適用する. > = U I > g > + > = x> g( x ) >. x { } 6. 第二レジスタ gx> ( ) を測定する. 第二レジスタの測定値は重要ではなく これ以降固定値になるの で 第二レジスタの表記を省略する. 測定後の状態は 下記のように書ける. > + > 3 > = ( α x > + α x > ) ここで α は実数であり i α + α = を満たす. 7. > 3 に Hadamard 変換を施す. ここで x i 対して z は i 4 > = ( H I ) 3 > x z x z > + > = α( ) + α( ) z> z { } x と z の法 の内積である. つまり xi = xi xi xi z = z z zに i i j j j= x z = x z mod. と計算される. 8. z> の qubit z z z > を測定する. 測定値は重要ではなく このレジスタの部分は これ以降固定されるので 表記を省略する. 測定後の状態は 下記のように書ける. 34
( ) > + > 5 > = β > + β > β β β β = > + > + > + >. ここで β は実数であり i β + = を満たす. β 9. 4 次の DCT 行列 C を > 5 に作用させる. > = C > 6 5 = γ > + γ > + γ >. 3 ここで γ i は実数であり γ + γ + γ = を満たす. なお 4 次の DCT 行列 C は 下記のような uitary 行列である. C 3 π 3π 5π 7π cos cos cos cos 8 8 8 8 = π 6π π 4π cos cos cos cos 8 8 8 8 3π 9π 5π π cos cos cos cos 8 8 8 8. > 6 の左側の qubit を測定する. 測定結果が ならば Step へ戻る. そうでなければ 以下の Step を続ける. これ以降 左側の qubit は固定されるので その表記を省略すると 測定後の状態は下記のようになる. > = δ > + δ >. 7 ここで δ は実数であり δ + δ = を満たす. i. > 7 を測定する. 測定結果が ならば カウンタ c の値を 増やし 測定結果が ならば カウン タ c の値を 増やす. そして Step へ戻る.. 最後に c c cos π ( 8 ) log ( + + cos π ( )) 8. 43 log + + cos π ( ) ( ) 8 であるならば を出力し そうでなければ を出力して終了する. g がランダム置換である事象を RP g が 対 ランダム関数である事象を RF と表記する. 35
Pr [ RP] = Pr [ RF ] = である. Step 6 の 3 > を場合分けして書くと > + > 3 > = x > 3 > = > + > 3 > = x > + x >. (4) ここで g がランダム置換ならば 3 > は必ず 3 > であり g が 対 ランダム関数ならば ψ 3 > は必ず 3 > である. つまり ψ Pr > = > RP = Pr > = > RP = Pr > = > RF = Pr > = > RF =. 3 3 3 3 ψ3 ψ3 ψ3 ψ3 Step 8 の > 5 を考えよう. 式 (4) から > 5 は 以下のいずれかの状態になる. > + > 5 > = > + > > + > 5 > = > > 5 > = > + > 5 > = > > + > 53 > = >. g をランダム置換と仮定する. このとき 5 > は > 5 または 5 > であり それぞれの確率 は / である. > 5 が > 5 または 53 > になることはない. つまり ψ ψ ψ 5 5 5 5 3 ψ Pr 5 > =5 > RP = Pr 5 > =5 > RP = Pr > = > RP = Pr > = > RP =. g を 対 ランダム関数と仮定する. > 5 は上記の四つのいずれかの状態になるが その確率は に依存する. が十分に大きくなると それぞれの状態になる確率は /4 に近くなる. Pr 5 > =5 > RF Pr 5 > =5 > RF Pr 5 > =5 > RF Pr 5 > =5 3 > RF. 4 Step 8 の測定は原像 x > あるいは x > + x > に関するほとんどの情報を破壊するので この時点で Step で得られた測定結果に対する原像の情報はほとんど失われる. このときに測定されなかった 36
qubit を用いて g の性質を特定する. Step 9 で DCT 変換を作用させた後の状態は 6 > = C ψ5 > = > 6 > = C 5 > π 3π = cos > cos > 8 8 6 > = 6 > = C ψ5 > π 3π = > + cos > cos > 8 8 63 > = C ψ53 > π 3π = > cos > + cos >. 8 8 Step において 測定結果 w が の確率を求めると Pr w = = Pr w = RP Pr RP + Pr w = RF Pr RF [ ] [ ] [ ] [ ] [ ] 5 3 π 3π = + cos cos. 967. 8 8 8 8 8 (5) 測定結果が として次のステップに進むと 測定後の状態 > 7 は 下記のいずれかになる. 7 > = > 7 > = > cos > = > + > π ( 8 ) π ( ) π ( 8 ) π ( ) 7 7 > = π + cos ( 8) + cos 8 cos 73 > = > >. π + cos ( 8) + cos 8 Step の測定結果を z とおくと z が または の確率は Pr [ z = RP] = Pr [ z = RP] = Pr [ z = RF ] = +. 598 π cos ( 8 ) + π cos ( 8 ) Pr [ z = RF ] = +. 48. π + cos ( 8 ) となる. g がランダム置換の場合 測定結果の分布は確率 / の二項分布であり g が 対 ランダム 関数の場合 測定結果の分布は確率約. 598 の二項分布になる. Step で行っていることは これら二 37
つの二項分布の識別を行っている. 例として c + c = の場合を考える. このとき Step の判定条件は c 59 ならば を出 力し c 5 ならば を出力することになる. したがって g [ ] [ ] g Pr g F ; A = Pr c 5 RF Pr g P ; A = Pr c 5 RP となる. それぞれについて 計算すると p = +. 598 π + cos ( 8 ) とおいて i i Pr [ c 5 RF ] = p ( p) i= 5 i. 74869 そして [ 5 RP] Pr c = i= 5 i. 73986 である. したがって rpr-advatage は rp r Adv q ( A). 74869. 73986 =. 467883 となる. ここで c + c = となるために必要なクエリ数 q は 式 (5) より 平均 79 である. 次に c + = の場合を考えよう. この場合 Step の判定条件は c 5987 ならば を出 5 c 力し c 5988 ならば を出力することになる. したがって g [ ] [ ] g Pr g F ; A = Pr c 5988 RF Pr g P ; A = Pr c 5988 RP となる. 上記と同様の計算により Pr c 5988 RF なので [ ] [ RP] Pr c 5988. 958 rp r Adv q ( A) 4 まとめ 量子アルゴリズムは 古典暗号の安全性を評価するツールとして有効である. 本研究では 古典暗号の安全性解析において重要なランダム置換とランダム関数の識別問題をとりあげ ランダム関数が 対 に限定される場合のそれらの識別困難性を検討した. その結果 クエリ回数が 回の場合 古典アルゴリズムでは 両者を識別することは不可能であるが 量子アルゴリズムでは 可能であることを示した. 本研究をまとめている段階で 本研究と関連ある先行研究結果をある国際会議の査読者から御指摘頂いた [][]. これら先行研究結果の比較 検討を今後行っていきたい. 38
謝辞 本研究にご援助頂いた財団法人電気通信普及財団に感謝します. 参考文献 [] S. Aaroso Quatum lower boud or the collisio problem Proceedigs o the 34th ACM Symposium o the Theory o Computig pp. 635 64. [] S. Aaroso ad Y. Shi Quatum lower bouds or the collisio ad the elemet distictess problems Joural o the ACM vol. 5 o. 4 pp. 595 65 July 4. [3] G. Brassard P. Hoyer ad A. Tapp Quatum algorithm or the collisio problem quat-ph/975 997. [4] L. K. Grover A ast quatum mechaical algorithm or database search Proceedigs o The 8th ACM Symposium o the Theory o Computig pp. 9 996. [5] S. Lucks The sum o PRPs is a secure PRF Advaces i Cryptology - EUROCRYPT Lecture Notes i Computer Sciece vol. 87 pp. 47 484. 発表資料 題名掲載誌 学会名等発表年月 7 Hawaii ad SITA Joit Idieretiable Double-Block-Legth Coerece o Iormatio 7 年 5 月 Compressio Fuctio Theory Query Complexity or Distiguishig Proceedigs o The 8 r-to-oe Radom Fuctios Symposium o Cryptography 8 年 月 ad Iormatio Security 39