無意識の擬似乱数関数

忘却擬似乱数関数（OPRF ）は、鍵付きハッシュ関数に似た暗号関数ですが、OPRFでは2つの当事者が協力して擬似乱数関数（ PRF）を安全に計算するという点が異なります。^[1]

具体的には、OPRF は次の特性を持つ 疑似ランダム関数です。

• 当事者は次を計算する：O = OPRF( I , S )
• ファーストパーティ（クライアント）は入力（I）を知っており、出力（O ）を学習しますが、秘密（S）は学習しません。
• 相手側（サーバー）は秘密（S）を知っていますが、入力（I）も出力（O）も知りません。
• この関数は、あらゆる（暗号的に安全な）疑似乱数関数と同じセキュリティ特性を持ちます。具体的には、出力を真の乱数と区別することが困難になります。

この関数は、相手側が関数の出力を知らないため、忘却型疑似乱数関数と呼ばれます。相手側は、結果の計算に参加しても新しい情報を得ることはありません。

ただし、秘密を保持するのはセカンドパーティのみであるため、ファーストパーティはセカンドパーティを関与させて疑似乱数関数(PRF) の出力を計算する必要があります。この要件により、セカンドパーティはアクセス制御、スロットリング、監査ログ、その他のセキュリティ対策 を実装できます。

従来の単一パーティによる擬似ランダム関数は1986年に初めて形式化されましたが^{[2] 、} 2パーティによる最初の忘却擬​​似ランダム関数が文献に記載されたのは1997年になってからでした^[3]。しかし、「忘却擬似ランダム関数」という用語は、同じ著者の何人かによって2005年まで造られませんでした^{[4] 。}

OPRF は暗号化や情報セキュリティの分野で多くの有用な用途があります。

これらには、パスワードベースの鍵導出、パスワードベースの鍵合意、パスワード強化、追跡不可能なCAPTCHA、パスワード管理、準同型 鍵管理、秘密集合交差などが含まれる。^{[1] [5]}

OPRF は準同型暗号化の特殊なケースと見なすことができます。これは、別の当事者が暗号化された入力に対して関数を計算し、結果 (暗号化されたまま) を生成できるため、計算内容については何も学習されないためです。

パスワードベースのキー導出のほとんどの形式は、フルレングスの 128 ビットまたは 256 ビットの暗号化キーと比較して、パスワードには通常、わずかなランダム性(またはエントロピー) が含まれるという問題を抱えています。このため、パスワードから導出されたキーはブルート フォース攻撃に対して脆弱になります。

ただし、パスワードを入力として受け取る OPRF の出力を使用することで、この脅威を軽減できます。

OPRF で使用される秘密鍵が高エントロピーである場合、OPRF の出力も高エントロピーになります。これにより、パスワードのエントロピーが低く、ブルート フォースによるクラッキングに対して脆弱であるという問題が解決されます。

この技術はパスワード強化と呼ばれます。^[6]これはキーストレッチと同様の目的を果たしますが、パスワード強化によりエントロピーが大幅に増加します。

さらに、このように強化されたパスワードを推測するたびにサーバーとのやり取りが必要になるため、オフライン攻撃が防止され、パスワードクラッキングの試みがあった場合にユーザーまたはシステム管理者に警告が送信されます。

回復されたキーは、認証（デジタル証明書と秘密キーを使用してPKI ベースの認証を実行するなど）に使用したり、暗号化されたファイルや暗号ウォレットなどの機密コンテンツを復号化するために使用したりできます。

パスワードは、一時的なセッション キーを確立し、クライアントとサーバーを相互に認証するためのキー合意プロトコルの基礎として使用できます。これは、パスワード認証キー交換( PAKE)と呼ばれます。

基本認証では、サーバーは認証の過程でユーザーのパスワードを取得します。サーバーが侵害されると、ユーザーのパスワードが公開され、ユーザーのセキュリティが侵害されます。

しかし、PAKE では、ユーザーのパスワードはサーバーに送信されないため、盗聴者の手に渡ることはありません。これは、ゼロ知識パスワード証明による認証と見ることができます。

PAKE のさまざまな「拡張形式」には、Oblivious Pseudorandom Function が組み込まれているため、認証中にサーバーはユーザーのパスワードを見ることはありませんが、それでもクライアントが正しいパスワードを所有していることを認証できます。これは、正しいパスワードを知っているクライアントだけが OPRF を使用して正しいキーを導出できると想定して行われます。

このようにOPRFを使用する拡張PAKEの例としてはOPAQUEがある。^{[7] [8] [9] [10]}

最近、OPRFはWhatsApp ^[11]やFacebook Messenger ^[12]の暗号化されたチャット履歴をバックアップするためのパスワードベースの鍵交換に適用されています。同様のユースケースがSignal Messenger ^[13]に追加される予定です。

CAPTCHA（「コンピュータと人間を区別するための完全に自動化された公開チューリングテスト」 ^[14]）は、自動化されたロボット（ボット）がウェブサイトにアクセスするのを防ぐためのメカニズムです。最近では、CAPTCHAテストを実行するメカニズムはGoogleやCloudFlareなどのサービスに集中化されていますが、これはユーザーのプライバシーを犠牲にする可能性があります。

最近、CloudFlareは「Privacy Pass」と呼ばれるプライバシー保護技術を開発しました^[15]この技術はOPRFに基づいており、クライアントのブラウザがCloudFlareからパスを取得し、それを提示してCAPTCHAテストをバイパスできるようにします。CloudFlareサービスはどのパスがどのユーザーに提供されたかを認識していないため、ユーザーとユーザーが訪問したウェブサイトを関連付けることはできません。これにより、ユーザーの追跡が防止され、ユーザーのプライバシーが保護されます。

パスワード マネージャーは、ユーザーに代わって多数の異なるアカウント資格情報を保持する可能性のあるソフトウェアまたはサービスです。パスワード マネージャーへのアクセスは機密性が非常に高く、攻撃を受けると多数の資格情報が攻撃者に公開される可能性があります。

OPRF に基づくパスワード マネージャーの最初の提案は SPHINX でした。^[16]これは、2 つのデバイス (ユーザーのラップトップと電話など) を使用し、それらが連携して特定のアカウント (ユーザー名と Web サイトのドメイン名で識別) のパスワードを計算します。ユーザーの 2 つのデバイスは OPRF プロトコルに従って値を交換するため、それらの間の接続を傍受しても、パスワードや各デバイスがパスワードの計算に使用した内部値については何も明らかにされません。パスワードの計算に 2 つのデバイスを必要とすることで、どちらかのデバイスが侵害されても、攻撃者がパスワードを計算できないことも保証されます。このアプローチの欠点は、ユーザーが自分のアカウントにログインするときには常に両方のデバイスにアクセスする必要があることです。

OPRFはMicrosoft Edgeのパスワードモニターによって使用され、ユーザーがブラウザに保存した資格情報が侵害されているかどうかをサーバーに照会できるようにします。このとき、この資格情報をサーバーに公開する必要はありません。^[17]

パスワード マネージャーによって管理されるパスワードを保護するのと同様に、OPRF を使用してキー管理システムのセキュリティを強化できます。

例えば、OPRFを使用すると、鍵管理システムは、ユーザーに提供する鍵を見たり、知ったり、知る立場に立つことなく、認証され許可されたユーザーに暗号鍵を発行することができます。^[18]

プライベート セットの交差は、2 つ以上の当事者がそれぞれのプライベート セットを比較して、共通するエントリを判別できるようにする暗号化技術ですが、共通していないエントリは公開されません。

たとえば、プライベート セットの交差を使用すると、ソーシャル ネットワークの 2 人のユーザーが、共通の友人が誰であるかを判別できますが、共通の友人がいない友人の ID は明らかにされません。これを行うには、友人の ID (たとえば、友人の電話番号や電子メール アドレス) に適用された OPRF の出力を共有します。

OPRFの出力を反転させてユーザーの身元を特定することはできず、OPRFはレート制限されているため、ブルートフォース攻撃（例えば、すべての電話番号を反復する攻撃）を防ぐことができます。^[19]

OPRF を実装するための基礎として使用できるさまざまな数学関数があります。

たとえば、楕円曲線の点乗算、素数に対するDiffie-Hellman剰余指数、 RSA署名計算などの非対称暗号化の方法などです。

楕円曲線と素数位数体を使用して OPRF を実装できます。基本的な考え方は、ファースト パーティ (クライアント) が入力をセカンド パーティに送信する前に 暗号化して隠す必要があるというものです。

このブラインド化は、セカンドパーティが実行する計算を生き残る暗号化の形式として考えることができます。したがって、ファーストパーティはセカンドパーティから受信した内容を復号化して「ブラインド化解除」することができ、その結果、入力がブラインド化されていなかった場合に受信したのと同じ結果を受け取ることができます。

相手側がブラインド入力を受信すると、秘密を使用して計算を実行します。この計算の結果は秘密を明らかにしてはなりません。

たとえば、相手側は楕円曲線上の点の乗算を実行する場合があります。または、大きな素数を法とするべき乗剰余演算を実行する場合があります。

ファーストパーティは、結果を受け取ると、ブラインド ファクターを認識した上で、セカンドパーティから返される結果に対するブラインド ファクターの影響を取り除く関数を計算します。これにより結果が「ブラインド解除」され、OPRF の出力 (または中間結果。クライアントは中間結果をハッシュするなどして、この中間結果を使用して OPRF の出力を計算します) が明らかになります。

以下は、楕円曲線ベースの OPRF を使用してクライアントとサーバーが実行する計算の 疑似コードです。

次のコードは、クライアントまたはファーストパーティによって実行される計算を表します。

byte [] computeOPRF ( byte [] input ) { // ポイントハッシュアルゴリズムを適用します// たとえば、RFC 9380 で説明されているように、ECPoint hashedPoint = hashToPoint ( input );   
    
    
       

    // ランダムなブラインド係数を生成する
Scalar b = randomScalar ();       

    // 曲線乗算を介して入力をブラインドします
ECPoint blindedInput = ECMultiply ( hashedPoint , b );        

    // 応答を取得するためにサーバーにリクエストを送信します
ECPoint serverResponse = sendRequest ( blindedInput );       

    // b の逆数を計算する
Scalar inverse = modInverse ( b );       

    // 応答を非ブラインド化して結果を生成します
ECPoint result = ECMultiply ( serverResponse , inverse );        

    // ブラインドされていない結果をハッシュして OPRF 計算を完了します。
return hash ( result ); }     

注:

クライアントはブラインド係数の逆数を計算します。これにより、ブラインド係数が結果に与える影響を逆転させ、クライアントが入力をブラインドしなかった場合にサーバーが返したであろう結果を取得できます。

最後のステップとして、OPRF を完了するために、クライアントは結果に対して一方向ハッシュを実行し、OPRF 出力が均一で、完全に疑似ランダムであり、逆変換不可能であることを確認します。

次のコードは、サーバーまたはセカンダリ パーティによって実行される計算を表します。

サーバーはクライアントからブラインド入力値を受け取り、リクエストを処理する前に認証、アクセス制御、リクエストスロットリング、またはその他のセキュリティ対策を実行する場合があります。次に、独自のシークレットを使用して次の値を計算します。

ECPoint processRequest ( ECPoint blindedInput , Scalar secret ) { // secret を適用して応答を計算しますECPoint response = ECMultiply ( blindedInput , secret ); return response ; }     
    
        
     

次に、ブラインド出力である応答をクライアントに返します。

注:

楕円曲線の点乗算は逆行列を計算するのが計算上難しいため (離散対数問題のように)、クライアントはサーバーの生成する応答からサーバーの秘密を実際に知ることはできません。

ただし、この関数は量子コンピュータによる攻撃に対して脆弱であることに注意してください。量子コンピュータを所有するクライアントまたは第三者は、与えられた入力に対して生成された結果を知って、サーバーの秘密を解読することができます。

ブラインド署名方式の出力が決定論的である場合、結果の署名をハッシュするだけで、OPRF を構築するための基礎として使用できます。

これは、ブラインド化により、ブラインド署名を計算する側は入力 (署名対象) も出力 (結果として得られるデジタル署名) も知ることができないためです。

OPRF 構造は、さまざまな方法で拡張できます。これには、検証可能、部分的に忘却可能、しきい値安全、量子耐性のあるバージョンが含まれます。

多くのアプリケーションでは、OPRF 出力が正しく計算されたことをファーストパーティが検証できる必要があります。たとえば、出力をデータの暗号化のキーとして使用する場合などです。間違った値が計算されると、暗号化されたデータは永久に失われる可能性があります。

幸いなことに、ほとんどの OPRF は検証可能性をサポートしています。たとえば、基礎構造としてRSAブラインド署名を使用する場合、クライアントは公開鍵を使用して、結果として得られるデジタル署名の正確性を検証できます。

楕円曲線やディフィー・ヘルマンベースのOPRFを使用する場合、公開鍵y = g ^xがわかれば、OPRFサーバーへの2回目のリクエストを使用して、前の結果の正しさのゼロ知識証明を作成することができます。^{[20] [21]}

OPRF に対する 1 つの変更は、部分的に認識されない PRF、または P-OPRF と呼ばれます。

具体的には、P-OPRF は次の特性を持つ関数です。

• 当事者は次を計算する：O = POPRF( H , E , S )
• ファーストパーティ（クライアント）は、隠された入力（H）と公開された入力（E）を知っており、出力（O ）を学習しますが、秘密（S）は学習しません。
• 相手側（サーバー）は秘密（S）を知っており、公開された入力（E ）を学習しますが、隠された入力（H）も出力（O ）も学習しません。

このユースケースは、サーバーが公開された入力 ( E ) に対して特定のスロットリングまたはアクセス制御を実装する必要がある場合です。たとえば、 ( E ) はファイル パスまたはユーザー名であり、サーバーはアクセス制御を適用し、要求元のユーザーが承認されている場合にのみ要求を処理します。

双線形ペアリングに基づくP-OPRFは「Pythia PRFサービス」で使用されました。^[22]

最近では、 IETF RFC 9497で標準化されたバージョンなど、ペアリングに基づかないP-OPRFのバージョンが登場しています。^[21]さらに最近の改良版もあります。^[23]

さらにセキュリティを強化するために、サーバーをしきい値化して、秘密 ( S ) が個々のサーバーによって保持されないようにすることが可能であり、そのため、単一のサーバー、または定義されたしきい値を下回るサーバーのセットが侵害されても、秘密が漏洩することはありません。

これは、各サーバーを秘密共有スキームの共有者にすることで実現できます。各サーバーは、結果を計算するのに自身の秘密を使用する代わりに、秘密の共有を使用して計算を実行します。

次に、クライアントはサーバーの計算結果のサブセットを取得し、指数の補間と呼ばれるプロトコルを計算するなどして、それらを組み合わせます。これにより、クライアントが完全な秘密を持つ単一のサーバーと対話した場合と同じ結果が回復されます。

このアルゴリズムは様々な分散暗号プロトコルで使用されています。^[24]

OPRFの効率的なポスト量子セキュリティ実装を見つけることは、活発に研究されている分野です。^[25]

「対称プリミティブに基づくOPRFを除いて、既知の効率的なOPRF構造はすべて、離散対数型または因数分解型の困難性仮定に依存しています。これらの仮定は、量子コンピュータの台頭とともに崩れることが知られています。」^[1]

例外として考えられるのは、格子ベースのOPRF ^[26]とアイソジェニーベースのOPRF ^[27]の2つですが、その効率性を改善し、安全性を確立するにはさらなる研究が必要です。アイソジェニーに対する最近の攻撃は、アルゴリズムの安全性に疑問を投げかけています。^[28]

量子耐性のある安全な OPRF を実現するための、より安全だが効率の悪いアプローチは、安全な 2 者間計算プロトコルを使用して、 AESやHMACなどの対称キー構造を使用して PRF を計算することです。

• ランダムオラクル
• 擬似ランダム関数群
• 無意識の転送
• 安全なマルチパーティ計算
• 暗号化プロトコル
• 準同型暗号