擬似乱数関数ファミリー

暗号理論において、擬似乱数関数族（ PRFと略記）とは、効率的に計算可能な関数の集合であり、以下の方法でランダムオラクルを模倣します。すなわち、効率的なアルゴリズムでは、PRF族からランダムに選択された関数とランダムオラクル（出力が完全にランダムに固定されている関数）を（有意な利点をもって）区別することはできません。擬似乱数関数は、暗号プリミティブ、特に安全な暗号化方式の構築において不可欠なツールです。

擬似乱数関数は、擬似乱数発生器（PRG）と混同してはならない。PRGの保証は、入力がランダムに選択された場合、単一の出力がランダムに見えるということである。一方、PRFの保証は、対応する入力がどのように選択されたかに関わらず、関数がPRFファミリーからランダムに抽出された限り、すべての出力がランダムに見えるということである。

擬似乱数関数ファミリーは、例えばGoldreich、Goldwasser、Micaliによって与えられた「GGM」構成を使用して、任意の擬似乱数生成器から構築できます。^{[ 1 ]}実際には、擬似乱数関数が必要なほとんどの場面でブロック暗号が使用されますが、ブロック暗号は一般に擬似乱数関数ファミリーを構成するものではありません。AES などのブロック暗号は、限られた数の入力と鍵サイズに対してのみ定義されているためです。^{[ 2 ]}

PRFは、効率的（つまり多項式時間で計算可能）で決定論的な関数であり、2つの異なる集合（定義域と値域）をマッピングし、真の乱数関数のように見える。

本来、真の乱数関数は、一様分布に従う乱数エントリで満たされたルックアップテーブルで構成されるはずです。しかし実際には、擬似乱数関数（PRF）は、定義域内の入力文字列と隠された乱数シードを与えられ、同じ入力文字列とシードで複数回実行され、常に同じ値を返します。とはいえ、任意の入力文字列が与えられた場合、シードが一様分布から取得されていれば、出力はランダムに見えます。

PRF（擬似乱数関数）は、その挙動が真の乱数関数と区別できない場合に優れているとみなされます。したがって、真の乱数関数またはPRFのいずれかから出力が得られた場合、その出力が真の乱数関数によって生成されたものかPRFによって生成されたものかを正しく判定する効率的な方法は存在しないはずです。

擬似乱数関数は入力を受け取ります${\displaystyle x\in \{0,1\}^{*}}$、 どこ${\displaystyle {}^{*}}$はクリーネ星です。入力サイズはどちらも${\displaystyle I=|x|}$出力サイズ${\displaystyle \lambda }$インデックスサイズのみに依存する${\displaystyle n:=|s|}$。

関数群、

${\displaystyle f_{s}:\left\{0,1\right\}^{I(n)}\rightarrow \left\{0,1\right\}^{\lambda (n)}}$

以下の条件が満たされる場合、擬似乱数である。

• 多項式時間で計算するアルゴリズムが存在する。${\displaystyle f_{s}(x)}$与えられたもの${\displaystyle s}$そして${\displaystyle x}$。
• させて${\displaystyle F_{n}}$関数の分布${\displaystyle f_{s}}$どこ${\displaystyle s}$は均一に分布しています${\displaystyle \{0,1\}^{n}}$、そして${\displaystyle RF_{n}}$すべての関数の集合上の均一分布を表す${\displaystyle \{0,1\}^{I(n)}}$に${\displaystyle \{0,1\}^{\lambda (n)}}$では、${\displaystyle F_{n}}$そして${\displaystyle RF_{n}}$は計算上区別不可能であり、nはセキュリティ パラメータである。つまり、どちらかからサンプリングされた関数のオラクルに問い合わせることができる攻撃者にとっては、${\displaystyle F_{n}}$または${\displaystyle RF_{n}}$彼女がどの種類の神託が与えられたかを区別できるという利点は、${\displaystyle n}$[ ^{3 ]​}

OPRF （Oblivious pseudorandom function）では、PRFに関与する2つの当事者から情報が隠蔽されます。^{[ 4 ]}つまり、アリスが秘密の値を暗号的にハッシュ化し、そのハッシュを暗号的にブラインド化してボブに送信するメッセージを作成し、ボブが秘密の値を混ぜて結果をアリスに返し、アリスがそれをアンブラインド化して最終出力を取得する場合、ボブはアリスの秘密の値も最終出力も見ることができず、アリスもボブの秘密の入力を見ることはできませんが、アリスは2つの入力のPRFである最終出力、つまりアリスの秘密とボブの秘密のPRFを見ることができます。^{[ 5 ]}これにより、信頼できない当事者間でも機密性の高い暗号情報のトランザクションを安全に行うことができます。

OPRFは、パスワード認証鍵合意のいくつかの実装で使用されています。^{[ 5 ]}

Microsoft Edgeのパスワードモニター機能では OPRF が使用されています。^{[ 6 ]}

PRFは以下のように使用できます。^{[ 7 ]}

1. 動的完全ハッシュ。攻撃者がハッシュ関数が以前のキーに割り当てた値に応じてキーの分布を変更できたとしても、攻撃者は衝突を強制することはできません。
2. 選択メッセージ攻撃に対して証明可能な安全性を備えた、決定論的でメモリレスな認証方式（メッセージ認証コードベース）を構築する。
3. 偽造不可能なID番号を配布する。このID番号は、少量のストレージしか持たないステーションによってローカルで検証可能である。
4. 敵味方識別システムの構築。

• 擬似乱数順列

• ゴールドライヒ、オデッド（2001）。暗号の基礎：基本ツール。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0-511-54689-1。
• パス、ラファエル、『暗号学入門』（PDF） 、 2015年12月22日取得