ランダムオラクル

暗号学において、ランダムオラクルとは、すべての固有のクエリに対して、その出力ドメインから均一に選択された(真に)ランダムな応答を返すオラクル(理論上のブラックボックス)です。クエリが繰り返されると、そのクエリが送信されるたびに同じように応答します。

言い換えると、ランダムオラクルとは、一様にランダムに選択された数学関数、つまり、各可能なクエリをその出力ドメインからの (固定された) ランダム応答にマッピングする関数です。

ランダムオラクルは、複雑性理論の文脈で初めて登場し、複雑性クラスの分離が相対化障壁に直面する可能性があると主張するために使用されました。最も顕著なケースはP対NP問題であり、1981年に2つのクラスがランダムオラクルに対してほぼ確実に異なることが示されました。^{[1]ランダムオラクルは、1993年に}ミヒル・ベラレとフィリップ・ロガウェイが出版した論文によって暗号学に取り入れられ、簡約証明で使用される正式な暗号モデルとして紹介されました。^[2]

これらは通常、暗号ハッシュ関数に関する弱い仮定を使用して証明を実行できない場合に使用されます。すべてのハッシュ関数をランダムオラクルに置き換えたときに安全であることが証明されたシステムは、暗号化の標準モデルで安全であるのではなく、ランダムオラクルモデルで安全であると説明されます。

アプリケーション

ランダムオラクルは、ハッシュ関数の出力に強いランダム性の仮定が必要なスキームにおいて、暗号ハッシュ関数の理想的な代替としてよく使用されます。このような証明は、攻撃者がオラクルに不可能な動作を要求するか、またはそれを破るために困難だと考えられている数学的問題を解かなければならないことを示すことで、システムまたはプロトコルが安全であることを示すことがよくあります。ただし、これはランダムオラクルモデルにおけるそのような特性を証明するだけであり、大きな設計上の欠陥が存在しないことを確認します。このような証明が標準モデルにおける同じ特性を意味するというのは、一般的には真実ではありません。それでも、ランダムオラクルモデルにおける証明は、正式なセキュリティ証明がまったくないよりはましだと考えられています。^[3]

暗号ハッシュ関数のすべての用途にランダムオラクルが必要なわけではありません。標準モデルで定義されている 1 つ以上の特性(衝突耐性、原像耐性、第 2 原像耐性など) のみを必要とする方式は、多くの場合、標準モデルで安全であることが証明できます (例: Cramer-Shoup 暗号システム)。

ランダムオラクルは計算複雑性理論において長い間検討されてきました^{[4] 。そして、}最適非対称暗号化パディング、RSA-FDH、PSSなど、多くの方式がランダムオラクルモデルで安全であることが証明されています。1986年に、アモス・フィアットとアディ・シャミール^[5]は、署名作成のためのプロトコルから相互作用を取り除くというランダムオラクルの主要な応用を示しました。

1989年にラッセル・インパグリアッツォとスティーブン・ルディッチ^[6]はランダムオラクルの限界、つまりランダムオラクルの存在だけでは秘密鍵の交換には不十分であることを示した。

1993年、ミヒル・ベラレとフィリップ・ロガウェイ^{[2]は、暗号構造におけるランダムオラクルの使用を初めて提唱しました。彼らの定義では、ランダムオラクルは、必要な長さに切り捨てることができる}無限長のビット文字列を生成します。

ランダムオラクルがセキュリティ証明内で使用される場合、それは敵対者を含むすべてのプレイヤーに利用可能になります。

ドメイン分離

1 つのオラクルは、各クエリの先頭に固定ビット文字列を付加することで、複数のオラクルとして扱うことができます (たとえば、"1|x" または "0|x" としてフォーマットされたクエリは、2 つの別々のランダムオラクルへの呼び出しと見なすことができます。同様に、"00|x"、"01|x"、"10|x"、および "11|x" は、4 つの別々のランダムオラクルへの呼び出しを表すために使用できます)。この方法は、通常、ドメイン分離と呼ばれます。オラクルのクローニングは、同じ証明内で一度構築されたランダムオラクルを再利用することです (これは実際には、1 つのアルゴリズム内で同じ暗号化ハッシュを異なる目的で複数回使用することに対応します)。^[7]不適切なドメイン分離によるオラクルのクローニングは、セキュリティ証明を破り、攻撃を成功させる可能性があります。^[8]

制限事項

チャーチ＝チューリングのテーゼによれば、有限アルゴリズムで計算可能な関数は真のランダムオラクルを実装することはできない（ランダムオラクルは、定義上、無限の数の入力が可能であり、出力はすべて互いに独立しており、任意の記述によって個別に指定する必要があるため、無限の記述を必要とする）。

実際、ランダムオラクルモデルでは安全であることが証明されているが、ランダムオラクルの代わりに実関数を使用すると明らかに安全でないことが証明されている、ある種の人為的な署名および暗号化方式が知られている。^[9]^[10]それにもかかわらず、より自然なプロトコルの場合、ランダムオラクルモデルでのセキュリティの証明は、プロトコルの実用的なセキュリティの非常に強力な証拠となる。^[11]

一般に、プロトコルが安全であることが証明された場合、そのプロトコルへの攻撃は、証明された範囲外であるか、証明の仮定の 1 つを破る必要があります。たとえば、証明が整数因数分解の困難性に依存している場合、この仮定を破るには、高速な整数因数分解アルゴリズムを発見する必要があります。代わりに、ランダムオラクル仮定を破るには、実際のハッシュ関数の未知の望ましくない特性を発見する必要があります。このような特性はありそうにないと考えられる優れたハッシュ関数の場合、検討中のプロトコルは安全であると見なすことができます。

ランダムオラクル仮説

Baker–Gill–Solovayの定理^{[12]は、 P}^A = NP ^Aとなるオラクル A が存在することを示したが、その後のBennettとGillによる研究^[13]は、ランダムオラクルB（{0,1} ⁿから {0,1} への関数で、各入力要素が他のすべての入力のマッピングとは独立に、確率 1/2 で 0 または 1 にマッピングされる）に対して、確率 1 で P ^B ⊊ NP ^Bとなることを示しました。同様の分離、およびランダムオラクルが確率 0 または 1 でクラスを分離するという事実（コルモゴロフのゼロ-1法則の結果として）から、ランダムオラクル仮説が生まれました。これは、2つの「許容可能な」複雑性クラス C ₁と C ₂が等しいのは、ランダムオラクルで（確率 1 で）等しい場合のみである（複雑性クラスの許容性は、BG81 ^[13]で定義されています）。この仮説は後に誤りであることが示され、ランダムオラクルAが確率1でIP ^A ⊊ PSPACE ^{Aであるにもかかわらず、許容可能な2つの複雑性クラス}IPとPSPACEが等しいことが示された^[14]。^[15]

理想的な暗号

理想的な暗号は、理想的なブロック暗号をモデル化するために使用されるランダム順列オラクルです。ランダム順列は、各暗号文ブロックを 1 つのプレーンテキストブロックに復号化し、その逆も同様であるため、 1 対 1 の対応が存在します。一部の暗号証明では、すべてのプレーヤーが「順方向」順列だけでなく「逆方向」順列も利用できるようになります。

^{最近の研究では、10ラウンド[16]}または8ラウンド^[17]の Feistelネットワークを使用したランダムオラクルから理想的な暗号を構築できることが示されています。

理想的な順列

理想順列は、出力がランダム順列と区別できない順列の動作をモデル化するために暗号化で使用されることがある理想化されたオブジェクトです。理想順列モデルでは、理想順列とその逆順列への追加のオラクルアクセスが与えられます。理想順列モデルは、理想暗号モデルの場合のように順列のファミリーではなく、単一の順列のみへのアクセスが与えられる、理想暗号モデルの特殊なケースと見なすことができます。

量子アクセス可能なランダムオラクル

ポスト量子暗号は、古典的な暗号方式に対する量子攻撃を研究する。ランダムオラクルとはハッシュ関数の抽象化であるため、量子攻撃者が量子重ね合わせのランダムオラクルにアクセスできると仮定するのは理にかなっている。^[18]古典的なセキュリティ証明の多くは、その量子ランダムオラクルモデルでは崩壊し、修正する必要がある。

参照

参考文献

^ベネット、チャールズ、 ギル、ジョン (1981)。「ランダムオラクル A に対して、N^A != NP^A != coNP^A、確率 1」。SIAM Journal on Computing : 96–113。doi : 10.1137/0210008。
^ ab Bellare, Mihir ; Rogaway, Phillip (1993). 「ランダムオラクルは実用的: 効率的なプロトコルを設計するためのパラダイム」ACM コンピュータおよび通信セキュリティ会議: 62–73. doi : 10.1145/168588.168596 . S2CID 3047274.
^ カッツ、ジョナサン、リンデル、イェフダ (2015)。現代暗号入門(第 2 版)。ボカラトン: チャップマン & ホール/CRC。pp. 174–175, 179–181。ISBN 978-1-4665-7027-6。
^ ベネット、チャールズ H. ; ギル、ジョン (1981)、「ランダムオラクル A に対して、P^A != NP^A != co-NP^A、確率 1」、SIAM コンピューティングジャーナル、10 (1): 96–113、doi :10.1137/0210008、ISSN 1095-7111
^ Fiat, Amos; Shamir, Adi (1986). 「自分自身を証明する方法: 識別と署名の問題に対する実用的な解決策」CRYPTO . pp. 186–194.
^ インパグリアッツォ、ラッセル、ルディッチ、スティーブン (1989)。「一方向順列の証明可能な結果の限界」。STOC : 44–61。
^ Bellare、Davis & Günther 2020、p. 3.
^ Bellare、Davis & Günther 2020、p. 4.
^ Ran Canetti、Oded Goldreich、Shai Halevi、「The Random Oracle Methodology Revisited」、STOC 1998、pp. 209–218 (PS および PDF)。
^ Craig Gentry と Zulfikar Ramzan。「Even-Mansour 暗号におけるランダム順列オラクルの排除」、2004 年。
^ Koblitz, Neal; Menezes, Alfred J. (2015). 「ランダムオラクルモデル：20年間の回顧」(PDF)。別の見方。 2015年4月2日時点のオリジナル(PDF)からアーカイブ。 2015年3月6日閲覧。
^ ベイカー、セオドア; ギル、ジョン; ソロベイ、ロバート (1975)。「P =? NP 問題の相対化」。SIAM J. Comput . 4 (4)。SIAM: 431–442。doi :10.1137/0204037。
^ abベネット、チャールズ; ギル、ジョン (1981)。「ランダムオラクル A に対して、P != NP != co-NP、確率 1」。SIAM J. Comput . 10 (1)。SIAM: 96–113。doi :10.1137/0210008。
^ シャミール、アディ（1992年10月）。「IP = PSPACE」。ジャーナルオブザACM。39（4）：869–877。doi ：10.1145/146585.146609。S2CID 315182 。
^ Chang, Richard; Chor, Benny ; Goldreich, Oded; Hartmanis, Juris; Hastad, Johan; Ranjan, Desh; Rohatgi, Pankaj (1994 年 8 月). 「ランダムオラクル仮説は誤り」. Journal of Computer and System Sciences . 49 (1): 24–39. doi : 10.1016/S0022-0000(05)80084-4 . ISSN 0022-0000.
^ Dachman-Soled, Dana; Katz, Jonathan; Thiruvengadam, Aishwarya (2016). 「10ラウンドのFeistelは理想的な暗号と区別できない」EUROCRYPT 2016 . Springer. pp. 649–678. doi :10.1007/978-3-662-49896-5_23.
^ Dai, Yuanxi; Steinberger, John (2016). 「8ラウンドFeistelネットワークの非差別性」CRYPTO 2016 . Springer.
^ Dan Boneh、Özgür Dagdelen、Marc Fischlin、Anja Lehmann、Christian Schaffner、Mark Zhandry (2011)。「量子の世界におけるランダムオラクル」。Advances in Cryptology – ASIACRYPT 2011。Lecture Notes in Computer Science。Vol. 7073。Springer。pp. 41–69。arXiv : 1008.0931。doi : 10.1007 / 978-3-642-25385-0_3。ISBN 978-3-642-25384-3。{{cite conference}}: CS1 maint: 複数の名前: 著者リスト (リンク)

出典

Bellare, Mihir; Davis, Hannah; Günther, Felix (2020)。「ドメインの分離: NIST PQC KEM、Oracle クローニング、読み取り専用非差別性」。暗号学の進歩 - EUROCRYPT 2020。コンピュータサイエンスの講義ノート。第 12106 巻。Cham: Springer International Publishing。pp. 3–32。doi :10.1007/978-3-030-45724-2_1。hdl : 20.500.11850 /392433。ISBN 978-3-030-45723-5. ISSN 0302-9743. S2CID 214642193.

[bennett-gill-1] ^ベネット、チャールズ、 ギル、ジョン (1981)。「ランダムオラクル A に対して、N^A != NP^A != coNP^A、確率 1」。SIAM Journal on Computing : 96–113。doi : 10.1137/0210008。

[bellrog-2] Bellare, Mihir ; Rogaway, Phillip (1993). 「ランダムオラクルは実用的: 効率的なプロトコルを設計するためのパラダイム」ACM コンピュータおよび通信セキュリティ会議: 62–73. doi : 10.1145/168588.168596 . S2CID 3047274.

[katz-3] カッツ、ジョナサン、リンデル、イェフダ (2015)。現代暗号入門(第 2 版)。ボカラトン: チャップマン & ホール/CRC。pp. 174–175, 179–181。ISBN 978-1-4665-7027-6。

[4] ベネット、チャールズ H. ; ギル、ジョン (1981)、「ランダムオラクル A に対して、P^A != NP^A != co-NP^A、確率 1」、SIAM コンピューティングジャーナル、10 (1): 96–113、doi :10.1137/0210008、ISSN 1095-7111

[5] Fiat, Amos; Shamir, Adi (1986). 「自分自身を証明する方法: 識別と署名の問題に対する実用的な解決策」CRYPTO . pp. 186–194.

[6] インパグリアッツォ、ラッセル、ルディッチ、スティーブン (1989)。「一方向順列の証明可能な結果の限界」。STOC : 44–61。

[FOOTNOTEBellareDavisGünther20203-7] Bellare、Davis & Günther 2020、p. 3.

[FOOTNOTEBellareDavisGünther20204-8] Bellare、Davis & Günther 2020、p. 4.

[9] Ran Canetti、Oded Goldreich、Shai Halevi、「The Random Oracle Methodology Revisited」、STOC 1998、pp. 209–218 (PS および PDF)。

[gentry_ramzan-10] Craig Gentry と Zulfikar Ramzan。「Even-Mansour 暗号におけるランダム順列オラクルの排除」、2004 年。

[anotherloook-11] Koblitz, Neal; Menezes, Alfred J. (2015). 「ランダムオラクルモデル：20年間の回顧」(PDF)。別の見方。 2015年4月2日時点のオリジナル(PDF)からアーカイブ。 2015年3月6日閲覧。

[BGS75-12] ベイカー、セオドア; ギル、ジョン; ソロベイ、ロバート (1975)。「P =? NP 問題の相対化」。SIAM J. Comput . 4 (4)。SIAM: 431–442。doi :10.1137/0204037。

[BG81-13] ベネット、チャールズ; ギル、ジョン (1981)。「ランダムオラクル A に対して、P != NP != co-NP、確率 1」。SIAM J. Comput . 10 (1)。SIAM: 96–113。doi :10.1137/0210008。

[14] シャミール、アディ（1992年10月）。「IP = PSPACE」。ジャーナルオブザACM。39（4）：869–877。doi ：10.1145/146585.146609。S2CID 315182 。

[CCGHHRR-15] Chang, Richard; Chor, Benny ; Goldreich, Oded; Hartmanis, Juris; Hastad, Johan; Ranjan, Desh; Rohatgi, Pankaj (1994 年 8 月). 「ランダムオラクル仮説は誤り」. Journal of Computer and System Sciences . 49 (1): 24–39. doi : 10.1016/S0022-0000(05)80084-4 . ISSN 0022-0000.

[DKT16-16] Dachman-Soled, Dana; Katz, Jonathan; Thiruvengadam, Aishwarya (2016). 「10ラウンドのFeistelは理想的な暗号と区別できない」EUROCRYPT 2016 . Springer. pp. 649–678. doi :10.1007/978-3-662-49896-5_23.

[C:DaiSte16-17] Dai, Yuanxi; Steinberger, John (2016). 「8ラウンドFeistelネットワークの非差別性」CRYPTO 2016 . Springer.

[Bon11-18] Dan Boneh、Özgür Dagdelen、Marc Fischlin、Anja Lehmann、Christian Schaffner、Mark Zhandry (2011)。「量子の世界におけるランダムオラクル」。Advances in Cryptology – ASIACRYPT 2011。Lecture Notes in Computer Science。Vol. 7073。Springer。pp. 41–69。arXiv : 1008.0931。doi : 10.1007 / 978-3-642-25385-0_3。ISBN 978-3-642-25384-3。{{cite conference}}: CS1 maint: 複数の名前: 著者リスト (リンク)