標準モデルにおける適応的セキュリティを備えた制約付き擬似乱数関数

概要

制約付き擬似乱数関数（CPRFs）は、入力空間のサブセットまたはある条件に基づいてPRFを評価できる「制約付き」PRF鍵の学習を可能にします。BonehとWaters [AC’13]、Kiayiasら [CCS’13]、Boyleら [PKC’14]により初めて導入されたこれらの関数は、多くの応用において有用な暗号化プリミティブとして示されてきました。これらの応用では、アドバーサリーがPRF値と制約付き鍵を任意の順序で学習できる「適応的セキュリティ」を要することが多くあります。しかし、任意の非自明な条件クラスに対して標準モデルでの標準仮定に基づく適応的セキュリティを備えたCPRFsの構成は知られていません。さらに、区別不能オブスキュレーション（IO）などの強力なツールに依存する場合でも、標準モデルにおける適応的セキュリティを備えたCPRFsの現状ではNC1条件のクラスにのみ対応しています。 本研究では、標準モデルにおける異なる種類の仮定から、さまざまな条件に対する新しい適応的セキュリティを備えたCPRFsを開発しました。我々の結果は以下にまとめられます。 • 1方向関数（OWFs）からt-論理積標準形（t-CNF）条件の適応的セキュリティとO(1)-コラージョン耐性を備えたCPRFsを構築します。ここで、O(1)-コラージョン耐性とは、アドバーサリーが定数個の制約付き鍵を取得できるという意味です。ここで、t-CNFはビット固定条件を特殊ケースとして含みます。 • 学習困難問題（LWE）仮定から内積条件の適応的セキュリティと単一鍵CPRFsを構築します。ここで、単一鍵セキュリティとは、アドバーサリーが1つの制約付き鍵のみを学習できるという意味です。ここで、内積条件は定数tのt-CNF条件を特殊ケースとして含みます。したがって、この構成は、第一の構成が対応するものよりより表現力豊かな条件のクラスをサポートしますが、コラージョン耐性を失い、より強い仮定に依存します。 • LWE仮定と区別不能オブスキュレーション（IO）からすべての回路の適応的セキュリティとO(1)-コラージョン耐性を備えたCPRFsを構築します。第一および第二の構成は、ランダムオラクルモデル外または強力な暗号化仮定に依存せずに、任意の非自明な条件に対して適応的セキュリティを達成した最初のCPRFsです。さらに、第一の構成は、この設定でコラージョン耐性のあらゆる概念を達成した最初のものでもあります。また、第一および第二の構成が弱い1鍵プライバシーを満たすことを証明しました。これは、制約付き鍵が対応する制約を明らかにしないことを概ね意味します。第三の構成は、標準モデルにおけるIOに基づく表現力が限られた条件のための適応的セキュリティを備えた従来のCPRFsよりも改善されています。