技術的サマリー：(疎な) LPN に対する硬度増幅

問題定義

本論文は、**ノイズ付きパリティ学習（LPN）問題およびその疎 LPN（Sparse-LPN）**バリアントを取り扱います。標準的な探索版の LPN（$LPN_{\eta, n, m}$）において、目的は、$m$ 個のノイズ付き線形サンプル $(A, b)$（ここで $b = As + e$）から秘密ベクトル$s \in \mathbb{F}_2^n$を復元することです。ここで、$A$は一様行列であり、ノイズベクトル$e$はパラメータ$\eta$ を持つ独立したベルヌーイ変数で構成されます。

疎 LPNバリアントでは、行列 $A$ の行が特定のハミング重み $\sigma$（しばしば $\sigma = O(1)$）を持つように制限されます。LPN は認証、公開鍵暗号、擬似乱数生成器など、さまざまな暗号プリミティブの基礎となる仮定として機能しますが、その平均ケースの硬度を確立することは依然として課題です。

ここで扱われる中心的な問いは、標準的なパラメータ変換の下で、ランダムなインスタンスの小さな割合 $\delta$ における硬度を、ほぼすべてのインスタンス（したがって平均ケースの硬度）における硬度に増幅できるかどうか、すなわち「ほぼ」最悪ケースから平均ケースへの帰着を証明できるかどうかです。LPN に対する既存の最悪ケースから平均ケースへの帰着は、コードの平滑化（smoothing）に依存しており、これは現在、極めて低い誤り率（暗号的領域とは程遠い）でのみ機能するか、あるいは問題をアルゴリズム的に容易にしてしまうパラメータを必要とします。疎 LPN については、暗号的領域においてそのような帰着は存在しません。

手法

著者らは、Hirahara と Shimizu [HS23] によって導入された直接積（direct-product）フレームワークに基づき、硬度の自己増幅アプローチを採用します。最悪ケースのインスタンスからの帰着を行う代わりに、平均ケース分布を直接扱い、インスタンスの小さな割合を解くことが、ほぼすべてのインスタンスを解くことを意味することを示します。

核心的な技術的戦略は、以下の 3 つの主要なステップから構成されます。

1. 直接積の埋め込み:
   著者らは、$n/k$ 次元の $k$ 個の独立した LPN インスタンスを、$n$ 次元の単一のより大きな LPN インスタンスに写す明示的な埋め込みを構成します。

   • $k$ 個のインスタンス $(A_i, b_i = A_i s_i + e_i)$ が与えられたとき、連結行列 $A = [A_1 | \dots | A_k]$ と、和をとった応答ベクトル $b = \sum b_i$ を形成します。
   • 得られるシステムは $b = As + e'$であり、ここで$s = (s_1, \dots, s_k)$ です。
   • 決定的に重要なのは、ノイズ分布が予測可能に変換されることです。2 値 LPN の場合、基底ノイズが $\eta$ であるとき、新しいノイズ率は $\eta' = \frac{1 - (1-2\eta)^k}{2}$ となります。$q$ 進 LPN の場合、$\eta' = 1 - (1-\eta)^k$ となります。
   • これにより、高いノイズを持つ単一の大きなインスタンスを解くソルバーを、同じ成功確率で低いノイズを持つ $k$ 個の独立した小さなインスタンスを解くソルバーに変換することが可能になります。

2. サンプリング分析による増幅:
   [HS23] のフレームワークを用いて、著者らは標準的な直接積帰着をサンプリング器として分析します。アルゴリズムが積分布（$k$ 重インスタンス）を確率 $\epsilon$ で解く場合、それを $1-\delta$ の入力割合において確率 $1-\delta$ で基底分布を解くアルゴリズムに変換できることを示します。これには $k = \Theta(\frac{1}{\delta} \log \frac{1}{\epsilon})$ が必要です。

3. 近似疎バリアントによる疎性の処理:
   標準的な疎 LPN は、行が正確に重み $\sigma$ を持つことを要求します。しかし、疎行列の連結は正確な疎性を保持しません。これを克服するため、著者らは近似疎バリアント（$LPN^{\approx \sigma}$）を導入します。これは、$A$ の各要素が確率 $\sigma/n$ で独立して 1 となるもので（結果として期待される行重みが $\sigma$ となります）。

   • この分布は連結埋め込みに対して閉じています。
   • 著者らは、この近似疎バリアントに対して自己増幅を証明します。
   • 最後に、近似疎バリアントから正確疎バリアント（$LPN^{=\sigma}$）へのフィルタリング帰着を提供します。正確に重み $\sigma$ を持たない行を破棄することで、サンプル数の制御された増大のみを伴って有効な正確疎インスタンスを回復します。

主要な貢献と結果

1. LPN に対するインスタンス割合の増幅:
   本論文は、任意の $\epsilon, \delta > 0$ に対して、成功確率 $\epsilon$ で $LPN_{\eta, n, m}$ を解くアルゴリズムを、スケーリングされたパラメータを持つ関連分布のインスタンスの $1-\delta$ 割合において確率 $1-\delta$ で成功するアルゴリズムに変換できることを証明します。これは 2 値体および $q$ 進体の両方に対して成り立ちます。

2. 疎 LPN に対する増幅:
   著者らはこれらの結果を疎 LPN に拡張します。近似疎バリアントに対する硬度の自己増幅を確立し、それを標準的な正確疎バリアントに帰着させます。これは、従来の平滑化ベースのアプローチが疎性を保持できなかったり、非暗号的なパラメータを必要としたりしていたのに対し、暗号パラメータ領域における疎 LPN として初の同種の結果です。

3. パラメータ領域:
   この増幅は、一定のノイズおよび $\eta = 1/n^\alpha$ までのノイズ率を含む、標準的な暗号ノイズ領域で成り立ちます。結果は、ガウス消去法が成功する「容易な」領域（例：$\eta \approx (\log n)/n$）にパラメータを強制するものではありません。

4. 検証と復号可能性:
   証明は、適切なパラメータに対して LPN インスタンスは高い確率で一意に復号可能であるという事実に依存しています。著者らは、ノイズベクトルが十分に小さく、符号距離が十分に大きいため、秘密の一意な回復が保証されることを示す厳密な境界（チェルノフ境界およびギルバート・ヴァルシャモフ型の議論を用いて）を提供します。

意義と主張

本論文は、LPN およびその疎バリアントの平均ケース硬度を仮定する際の基盤を強化することを主張します。インスタンスの小さな割合における硬度が、ほぼすべてのインスタンスにおける硬度を意味することを示すことで、完全な最悪ケースから平均ケースへの帰着に代わる「次善の策」を提供します。

• LPN に対して: LPN の平均ケース硬度が堅牢であることを確立します。敵対者が入力のある無視できない割合で問題を破ることができれば、それを増幅してほぼすべての入力で破ることが可能になります。
• 疎 LPN に対して: 文献における重要なギャップを解消します。LWE と異なり、疎 LPN には最悪ケースから平均ケースへの帰着が存在しませんでした。この研究は、暗号領域における疎 LPN に対する初の自己増幅結果を提供し、区別不能性オブリビエーションや擬似乱数生成器などの構成におけるその使用を正当化します。

著者らは明示的に、エントロピー制約と疎性の破壊により疎インスタンスに対して失敗する「レフトオーバーハッシュ」スタイルの平滑化のボトルネックを回避するアプローチを採用していると指摘しています。代わりに、彼らの直接積埋め込みは問題の構造を保持しつつ硬度を増幅します。彼らは、同様のパラメータを持つ真の最悪ケースから平均ケースへの帰着を達成する可能性を未解決の問題として残し、その結果をその目標に向けた重要な一歩として位置づけています。