💻 computer science

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$ , Generically)

本論文は、弱いPRFを最小限の深さオーバーヘッドで強いPRFへと変換する汎用的な変換を導入するものであり、これによりLWE、LPN、およびCDHを含む標準的な仮定からの $\mathsf{NC}^1$ 計算可能なPRFの構築を可能にし、低次数の暗号理論における長年の未解決問題を解決する。

原著者： Youlong Ding, Aayush Jain, Ilan Komargodski

公開日 2026-08-27

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Youlong Ding, Aayush Jain, Ilan Komargodski

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

デジタル界において、セキュリティはしばしば「擬似乱数関数」と呼ばれる特別な種類の数学的ツールに依存しています。ある秘密のコードとデータを受け取り、それを見ていても完全にランダムに見える数字の列を吐き出す機械を想像してみてください。もしその機械が正しく動作していれば、その出力と真の乱数配列との違いを、たとえその機械が何度も動作する様子を見てきたとしても、誰も判別することはできません。これらのツールは、オンラインバンキングからプライベートなメッセージに至るまで、あらゆるものを保護している目に見えない錠前であり、鍵なのです。長年、研究者たちは、これらの機械をできるだけ速く、具体的には極めて少ないステップで動作させるようにすることに注力してきました。コンピュータサイエンスの言葉を使えば、これは非常に「浅い（shallow）」回路を用いて構築することを意味し、これにより現代のプロセッサ上で計算がほぼ瞬時に行えるようになります。これらのツールが速く、かつ単純であればあるほど、安全な投票やプライベートなデータ共有のような複雑なシステムにおいて、より効率的に活用できるのです。

長い間、これらのような高速で浅い機械を構築する能力には、頑固なギャップが存在していました。私たちは、非常に強力で複雑な数学的仮定を用いて、それらを構築する方法を知っていましたが、それらは深く、遅い回路を必要としました。逆に、浅い回路を構築することはできましたが、それはより弱く、十分に証明されていない仮定や、非常に特殊で硬直した数学的構造に頼る場合に限られていました。それは、ドアを開けることはできるが持ち運ぶには重すぎる鍵を持っているか、あるいは、軽い鍵を持っているが、それはたった一つの奇妙な錠前でしか機能しないような状態でした。目標は、最も標準的で信頼できる錠前のみを使用して、あらゆるドアを開けることができる軽量な鍵を作る方法を見つけることでした。この課題は30年近くも立ちはだかり、デジタル世界のセキュリティを効率化することを制限してきました。

ある研究チームが、弱い、あるいは構築しやすいツールを、速度を落とすことなく強力で安全なものへと変換する、新しい汎用的な手法によって、このギャップを埋めました。「Pseudorandom Functions in NC1 from LWE/LPN/CDH」と題された論文で発表された彼らの研究は、最も基本的で広く信頼されている3つの数学的仮定を用いて、これらの高速で浅い機械を構築することが可能であることを実証しました。研究者たちは、複雑な関数を小さな計算のツリー（木構造）を通じて構築する「GGM構成」と呼ばれる古いアイデアを洗練させることで、これを達成しました。従来の方法は、一歩進むごとに同じ量の労力を必要とする長い廊下を歩くようなものであり、その結果、全体の道のりは長く、遅いものになっていました。新しい手法はこの廊下の形を変えます。プロセスがツリーの深部へと進むにつれて、各ステップで必要とされる作業量は幾何級数的に減少していきます。最初の数ステップは重い作業ですが、その後のステップは非常に速く軽くなっていくため、総計の労力は小さいまま保たれます。この「テーパリング（先細り）」技術により、研究者たちはプロセス全体を浅い、高速な回路の範囲内に収めることができたのです。

この新手法が機能することを証明するために、チームは解決が困難であることで知られる3つの特定の数学的問題にこれを適用しました。第一の課題は「誤差を伴う学習（Learning With Errors）」問題であり、これはノイズを含むデータセットの中から隠れたパターンを見つけ出すものです。この問題から高速な機械を構築しようとする過去の試みでは、非常に大きな数を用いた、より複雑で特殊なバージョンの数学を必要としていました。今回の新しい研究は、はるかに小さな数を用いる標準的なバージョンでも十分であることを示しました。第二の課題は「ノイズを伴うパリティ学習（Learning Parity with Noise）」であり、これはランダムに反転されたビットのストリームから隠れたパターンを見つけ出すものです。研究者たちは、彼らの手法がこの問題の標準的なバージョンで動作することを示し、以前必要とされていた特殊で構造化されたバージョンの必要性を排除しました。第三の課題は、インターネットセキュリティの礎石であり、秘密鍵の交換に使用される「計算ディフィー・ヘルマン（Computational Diffie-Hellman）」仮定です。数十年にわたり、この仮定から高速な機械を構築する唯一の既知の方法は、より強力で制約の強いバージョンの問題に依存していました。新しい構成は、標準的なバージョンで十分であることを証明しました。

この研究の重要性は、その汎用性と標準的な仮定への依存にあります。弱い、浅いツールを、深さを増すことなく強力で安全なものへとアップグレードできることを示すことで、研究者たちは最も基本的でよく研究されている数学的問題から、高速で安全な関数を構築する道を切り開きました。これは、この分野におけるいくつかの長年の疑問を解決し、将来の暗号システムのための新しい、柔軟な設計図を提供します。研究者たちは、これが可能であると示唆しただけではありません。具体的な、ステップ・バイ・ステップの構成と、それが機能するという厳密な証明を提供しました。彼らは、結果として得られる機械の深さが、元のツールの深さと実質的に同じであることを示し、速度の利点を維持したまま、必要なセキュリティを獲得できることを実証したのです。

この成果は、初めて、私たちが最も一般的で信頼されている数学的基礎を用いて、速度を犠牲にすることなく、これらの不可欠なセキュリティツールを構築できることを意味します。これは、効率性のために以前は必要だと考えられていた、特殊で複雑な変種を使用する必要性をなくします。その結果、将来のデジタルセキュリティのための、より堅牢で多用途な基盤が築かれ、幅広いテクノロジーに展開可能な、より高速で効率的な暗号化手法が可能になります。この研究は、「弱い、速いツール」と「強い、速いツール」の間の障壁が打破されたことを示す決定的な証明であり、効率的な暗号設計の新時代への扉を開くものです。

技術要約：LWE/LPN/CDHからのNC1における擬似乱数関数

1. 問題設定

低い並列計算量（具体的には、多項式サイズの回路によって計算可能なクラス NC1 内）を持つ擬似乱数関数（PRF）の構築は、暗号理論における長年の未解決問題であった。PRFは、ゴールドライヒ・ゴールドワッサー・ミカル（GGM）変換を通じて擬似乱数生成器（PRG）から一般的に構築できるが、この手法は本質的に逐次的である。たとえ基礎となるPRGが対数深さで計算可能であっても、結果として得られるPRFは $\omega(\log n)$ の深さを必要とし、NC1からは外れてしまう。

本研究以前に知られているNC1計算可能なPRFは極めて少なく、高度に特定の代数的構造や強い仮定に依存していた：

Naor-Reingold (1997, 2004): 決定的ディフィー・ヘルマン（DDH）および素因数分解から $TC_0 \subseteq NC1$ 内のPRFを構築した。
Banerjee-Peikert-Rosen (2012): Ring-LWEから $TC_0$ 内のPRFを構築したが、超多項式のモジュラス対ノイズ比を必要とした。
Ding-Jain-Komargodski (2025): SeededLPNやRing-LPNといった、構造化されたLPNの変種からPRFを構築した。

中心となる課題は、構造化された変種や超多項式のパラメータに依存することなく、標準的な仮定（多項式モジュラス対ノイズ比を持つLWE、標準的なLPN、および計算的ディフィー・ヘルマン）からNC1計算可能なPRFを実現することである。

2. 手法

本論文は、弱擬似乱数関数（WPRF）から強固なPRFへの汎用的な深さ保存変換と、標準的な仮定からの**新しい深さ効率的なWPRF（またはシンセサイザ）**の構築という、二段構えのアプローチを導入している。

2.1 Tapering-GGM: 汎用的な変換

著者らは、GGMツリー構成の新しい適応版であるTapering-GGMを提案し、WPRFを強固なPRFへとアップグレードしつつ、評価回路の深さを保存する。

テーパリング機構: 標準的なGGMツリーでは、状態サイズは一定であり、深さはツリーのレベル数（ $\ell \cdot d_{WPRF}$ ）に対して線形に蓄積する。Tapering-GGMでは、状態サイズが各レベルで幾何級数的に減少する。レベル $i$ におけるセキュリティパラメータを $\lambda^{(i)}$ とすると、著者らは $\lambda^{(i)} = \lambda^{2^{-i+1}}$ と定義する。その結果、レベル $i$ におけるWPRF呼び出しの深さ $d(\lambda^{(i)})$ は幾何級数的に減少する。
深さの解析: 基礎となるWPRFの深さが $d(\lambda) = \Theta(\log \lambda)$ である場合、Tapering-GGM構成の総深さは以下のようになる：
$d_{total} = O(\log \lambda) + \sum_{i=1}^{\ell} d(\lambda^{(i)}) \approx O(\log \lambda) + \sum_{i=1}^{\ell} \log(\lambda^{2^{-i+1}}) = O(\log \lambda)$
この幾何学的な減衰により、総深さは $O(d(\lambda))$ に維持され、入力WPRFがNC1にある場合、構成全体もNC1に留まることが保証される。
セキュリティ上の課題と解決策:
- 課題: ツリーが深くなるにつれ、セキュリティパラメータ $\lambda^{(i)}$ が小さくなり（劣多項式）、基礎となるWPRFの計算論的安全性が崩れる可能性がある。
- 解決策1（ハッシング）: 入力はまず、ペアワイズ独立なハッシュ関数によってハッシュされる。これにより、高い確率で、攻撃者のクエリは、セキュリティパラメータが依然として多項式である上位 $O(\log_\Delta q)$ レベル内で「砕け散り」（異なるパスにマッピングされ）、「分散」される。
- 解決策2（鍵の一様性）: 砕け散るポイントより下のレベルについては、情報理論的セキュリティに依存する。著者らは、WPRFが鍵一様（key-uniform）（1-wise independent）であることを要求する。砕け散るレベルにおける状態が擬似乱数であれば、その後の鍵一様な変換の合成は、下位レベルのWPRFの計算論的な困難さに関わらず、この状態を完全に一様な出力へと写像する。

2.2 深さ効率的なWPRFの構築

著者らは、標準的な仮定からの新しいWPRF構成を用いて、Tapering-GGMフレームワークを具体化している：

LWE (Learning With Errors) から:
- 著者らは、多項式モジュラス対ノイズ比（ $\alpha = n^{-\epsilon}$ ）を持つ標準的なLWEから、初のNC1 WPRFを構築した。
- 主要な技術的ツール: $O(\text{poly}(\log \log \lambda))$ の深さで計算可能なRounded Gaussian Sampler。彼らは、 $\ln$ 、 $\cos$ の低次多項式近似および平方根のためのニュートン反復法を用いて、ボックス＝ミュラー変換を近似している。
- 構成: Kim [Kim20] に着想を得た連鎖（chaining）パラダイムを採用している。この構成は、マスクされたLWEの内積を層ごとに計算する。ある層の出力の高次ビットが、次の層の誤差分布を決定論的にサンプリングする。誤差サンプラーの有界性は安定性を保証し、ハイブリッド引数によるセキュリティ証明を可能にする。
LPN (Learning Parity with Noise) から:
- 著者らは、標準的なLPN（任意の逆多項式ノイズ）からNC1内のWPRFを提供する、Ding, Jain, および Komargodski [DJK25] による最近の結果を活用している。
- これをTapering-GGMと組み合わせることで、先行研究で必要とされた構造化された変種（例：Ring-LPN）を排除し、標準的なLPNからの初のNC1 PRFを得ている。
CDH (Computational Diffie-Hellman) から:
- 著者らは、Tapering-GGMが実際にはWPRFよりも弱いプリミティブ、すなわちシンセサイザ（入力プールが攻撃者から隠されているもの）を必要とすることに注目した。
- 彼らは、NC1で計算可能なNaor-Reingoldのシンセサイザ構成 [NR95, NR99] を用いてこの変換を具体化している。これにより、DDHに基づく従来の構成を改善し、CDH仮定の下での初のNC1 PRFを実現した。

3. 主な貢献

汎用的な深さ保存変換: 任意の（深さ $d(\lambda) = \Omega(\log \lambda)$ で計算可能な）WPRF（またはシンセサイザ）を、深さ $O(d(\lambda))$ で計算可能な強固なPRFへと変換するブラックボックス変換。これは、標準的な仮定からNC1 PRFを得ることを妨げていた一般的な障壁を解消するものである。
標準的なLWEからのNC1 PRF: 多項式モジュラス対ノイズ比 $\alpha = n^{-\epsilon}$ を持つ標準的なLWEから、初のNC1 WPRFを構築した。これは、Vaikuntanathanの講義ノートに明記されていた未解決問題を解決するものである。これは、多項式近似係数 $\tilde{O}(n^{1+\epsilon})$ 内でのGapSVPの困難さに依存している。
標準的なLPNからのNC1 PRF: 標準的なLPN仮定からの初のNC1 WPRFを構築し、Ring-LPNやSparse LPNのような構造化された変種への依存を排除した。
CDHからのNC1 PRF: CDH仮定の下での初のNC1 PRFを構築し、より強いDDHに依存していた30年前のNaor-Reingoldの結果を改善した。
低深さのガウス・サンプラー: $O(\text{poly}(\log \log \lambda))$ の深さで丸められたガウス誤差をサンプリングする、新しい決定論的回路。これはLWEベースのWPRFの重要な構成要素である。

4. 結果

本論文は以下の具体的な結果を確立している：

定理: もしNC1内にWPRFが存在するならば、NC1内にPRFが存在する。
系 (LWE): ノイズ対モジュラス比 $\alpha = n^{-\epsilon}$ に対してLWE仮定が成立すると仮定すれば、NC1内にPRFが存在する。
系 (LPN): ノイズ確率 $\mu = n^{-\epsilon}$ に対してLPN仮定が成立すると仮定すれば、NC1内にPRFが存在する。
系 (CDH): CDH仮定が成立すると仮定すれば、NC1内にPRFが存在する。
系 (GapSVP): GapSVPが $\tilde{O}(n^{1+\epsilon})$ の範囲内で近似困難であると仮定すれば、NC1内にPRFが存在する。

5. 意義

本論文は、暗号プリミティブの計算量におけるいくつかの長年の未解決問題を解決すると主張している。PRF評価の深さをGGM変換の逐次的な性質から切り離すことにより、著者らは、並列効率を犠牲にすることなく、幅広い標準的な仮定から強固なPRFが構築できることを示した。

具体的には、本研究は以下の成果を挙げている：

NC1 PRFのためのRing-LWEおよび超多項式パラメータへの依存を排除し、標準的なLWE（多項式パラメータ）へと移行した。
構造化されたLPNの変種への依存を排除し、標準的なLPNへと移行した。
CDHベースのPRFの困難な仮定を、DDHからCDHへと弱めた。
既存の（例えば [ABG+14], [AR16] による）ログ深さのWPRF候補を、基礎となる仮定が成立する限り、ログ深さのPRFへとアップグレードできる汎用的なフレームワーク（Tapering-GGM）を提供した。

著者らは、本研究を、暗号の並列計算量を理解するための基礎的なステップとして位置づけており、安全な計算プロトコル、学習理論（PRF対学習の接続を介して）、およびメタ複雑性への影響を示唆している。