擬似ランダム関数群

暗号学において、擬似乱数関数ファミリ(略称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 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}$
• が上で一様分布する関数の分布とし、がからまでのすべての関数の集合上の一様分布を表すとします。すると、 と は計算上区別がつかないことが求められます。ここで、nはセキュリティパラメータです。つまり、またはからサンプリングされた関数のオラクルに対してクエリを実行できる攻撃者にとって、どの種類のオラクルが自分に与えられているかを区別できるという利点は では無視できるほど小さいということです。^[3]${\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}}$${\displaystyle F_{n}}$${\displaystyle RF_{n}}$${\displaystyle n}$

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

OPRFはパスワード認証鍵共有のいくつかの実装で使用されます。^[5]

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

Oblivious Pseudorandom Functionsのメイン記事を参照してください。

PRFは以下の用途に使用できます: ^[7]

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

• 擬似ランダム順列

• Goldreich, Oded (2001)。『暗号の基礎：基本ツール』。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0-511-54689-1。
• パス、ラファエル、暗号化講座(PDF) 、 2015 年12 月 22 日取得