擬似乱数順列

暗号学において、擬似乱数置換（PRP）とは、実際的な努力ではランダム置換（つまり、関数の定義域上のすべての置換の族から一様な確率でランダムに選択された置換）と区別できない関数のことである。

Fを写像とする$\displaystyle \left\{0,1\right\}^{n}\times \left\{0,1\right\}^{s}\rightarrow \left\{0,1\right\}^{n}}$Fが PRP であるのは、以下の条件を満たす場合のみです。

• いかなる場合でも${\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}}$、。
• すべての確率的多項式時間判別器について${\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}}$nビット文字列の順列の集合から一様にランダムに選択される。^{[ 1 ]}

擬似乱数順列族とは、擬似乱数順列の集合であり、特定の順列は鍵を用いて選択することができる。

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

現代の暗号には、超擬似乱数性が求められる。つまり、攻撃者が暗号の順方向と逆方向の両方にブラックボックスアクセスできたとしても、暗号は同じメッセージ空間上のランダムに選択された順列と区別できないはずである。^{[ 3 ]}

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

• DES

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

• AES-128

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

• ブロック暗号（固定サイズのビットブロックに対して動作する擬似乱数置換ファミリー）
• フォーマット保持型暗号化（任意の有限集合上で動作する擬似乱数置換族）