擬似ランダム順列

暗号学において、擬似ランダム順列 (PRP)とは、実際的な努力ではランダム順列(つまり、関数のドメイン上のすべての順列のファミリから均一な確率でランダムに選択された順列)と区別できない関数です。

F を写像とする。FがPRP であるのは、 ${\displaystyle \left\{0,1\right\}^{n}\times \left\{0,1\right\}^{s}\rightarrow \left\{0,1\right\}^{n}}$

• 任意の に対して、は からへの全単射です（ただし ）。${\displaystyle K\in \left\{0,1\right\}^{s}}$${\displaystyle F_{K}}$${\displaystyle \left\{0,1\right\}^{n}}$${\displaystyle \left\{0,1\right\}^{n}}$${\displaystyle F_{K}(x)=F(x,K)}$
• 任意の に対して、任意のを評価する「効率的な」アルゴリズムが存在します。${\displaystyle K\in \left\{0,1\right\}^{s}}$${\displaystyle F_{K}(x)}$${\displaystyle x\in \left\{0,1\right\}^{n}}$
• すべての確率的多項式時間識別子 について: 、ここで は一様ランダムに選択され、 はnビット文字列上の順列の集合から一様ランダムに選択される。^[1]${\displaystyle D}$${\displaystyle \left|Pr\left(D^{F_{K}}(1^{n})=1\right)-Pr\left(D^{f_{n}}(1^{n})=1\right)\right|<\varepsilon (s)}$${\displaystyle K\in \left\{0,1\right\}^{s}}$${\displaystyle f_{n}}$

疑似ランダム順列ファミリは、キーを使用して特定の順列を選択できる疑似ランダム順列のコレクションです。

（鍵付き）ブロック暗号の理想的な抽象化は、平文と暗号文のマッピングにおける真にランダムな順列です。ブロック暗号のセキュリティパラメータで指定されたよりも少ない労力で大きな利点を実現する際立ったアルゴリズムが存在する場合（これは通常、必要な労力が暗号の鍵空間を総当たりで探索するのとほぼ同じであることを意味します）、そのような破綻が直ちに実際のセキュリティ違反につながらないとしても、少なくとも認証の意味で暗号は破られたとみなされます。^[2]

現代の暗号は超擬似乱数性を持つことが期待されています。つまり、たとえ敵対者が暗号の順方向と逆方向へのブラックボックスアクセスを持っていたとしても、暗号は同じメッセージ空間上でランダムに選択された順列と区別がつかないはずです。 ^[3]

マイケル・ルビーとチャールズ・ラックオフ^[4]は、フェイステル暗号を用いて構築されたルビー・ラックオフ構造を用いて擬似乱数関数から「強力な」擬似乱数順列を構築できることを示した。

予測不可能な順列( UP ) F k_は、高速ランダム化アルゴリズムによって値を予測できない順列です。予測不可能な順列は、より複雑な特性を持つ暗号化システムの基礎となる暗号化プリミティブとして使用できます。

予測不可能な順列に対する攻撃者は、順方向と逆方向の順列演算の両方についてオラクルにアクセスできるアルゴリズムとして定義されます。攻撃者はチャレンジ入力k を与えられ、 F _kの値を予測するように求められます。この予測を行うためにオラクルに一連のクエリを実行することは許可されていますが、 kの値自体をクエリすることは許可されていません。^[5]

順列を生成するランダム化アルゴリズムは、その出力が長さn のバイナリ文字列で記述されたアイテムのセットに対する順列である場合、予測不可能な順列を生成します。その順列は、チャレンジ ラウンドの前にオラクルに対して多項式 ( nの多項式) 個のクエリを実行し、実行時間がnの多項式であり、すべてのインスタンスのエラー確率が 1/2 未満である敵対者によって、ランダムよりも大幅に優れた精度で予測できない場合に生成されます。つまり、順列のオラクルによって相対化された複雑性クラス PP では予測できません。[ 5 ^]

関数F _{k は}、予測不可能性の要件のみを満たす場合、安全なメッセージ認証コード(MAC)ではないことが示されます。また、 nビットの UP としてモデル化されたブロック暗号から、効率的な可変入力長 MAC を構築することはできないことも示されます。予測不可能なラウンド関数を使用したk  =  n / ω (log  λ ) ラウンドの Feistel 構造の出力は、すべての中間ラウンド値を漏らす可能性があることが示されています。 ^[5]現実的な予測不可能な関数 (UF) であっても、中間ラウンド値に関する部分的な情報が出力を通じて漏らされる可能性があります。後に、Feistel 構造で超対数ラウンド数を使用すると、敵対者がすべての中間ラウンド値と順列出力を取得しても、結果として得られる UP 構造は安全であることが示されました。^[6]

この点に関して証明された定理もある。それは、 UP構築 ψ _U,kに対する予測不可能性ゲームで無視できない優位性 ε π を持ち、_{チャレンジャーに}多項式数のクエリを行う効率的なUP敵対者 A π が存在する場合、UFファミリー F からサンプリングされたUFに対する予測不可能性ゲームで無視できない優位性を持つUF敵対者 A f も存在するというものである。このこと から_、 UP敵対者A _πの最大優位性はε _π = O ( ε _{f .} ( qk ) ⁶ )であることが示される。ここでε _{f は}、 FからサンプリングされたUFに対して時間 O( t + ( qk ) ⁵ ) で実行されるUF敵対者の最大優位性を表し、tはPRP敵対者A _ψの実行時間、q はそれが行ったクエリの数である。^{[6] [7]}

さらに、予測不可能性という特性を満たし、必ずしも疑似ランダム性を満たさない署名方式は、本質的には検証可能予測不可能関数 (VUF) です。検証可能予測不可能関数は、検証可能疑似ランダム関数 (VRF) と同様に定義されますが、疑似ランダム性がより弱い予測不可能性に置き換えられています。検証可能予測不可能な順列は、VUF の順列アナログ、または VRP の予測不可能なアナログです。VRP は VUP でもあり、VUP は実際には VRF に適用された Feistel 構成を介して VRP を構築することで構築できます。しかし、VUF は VRF よりも構築がはるかに簡単であるため、これは有用とは見なされていません。^[8]

• デス

K x X → X ∀ X={0,1} ⁶⁴、K={0,1} ⁵⁶

• AES-128

K x X → X ∀ k=X={0,1} ¹²⁸

• ブロック暗号（固定サイズのビットブロック上で動作する擬似ランダム順列ファミリ）
• フォーマット保存暗号化（任意の有限集合上で動作する擬似ランダム順列族）