技術要約：低ノイズLPNにおける最悪ケースの困難性に向けて

問題提起

Learning Parity with Noise (LPN) 問題は、暗号理論における基礎的な仮定であり、対称鍵プリミティブや公開鍵暗号（PKE）の基盤となっている。類似の Learning With Errors (LWE) 問題の平均ケースの困難性は最悪ケースの格子仮定によって支持されている一方で、LPNに対して同様の最悪ケースから平均ケースへの帰着を確立することは、依然として中心的な未解決問題である。

Brakerskiら [BLVW19] や YuおよびZhang [YZ21] による既存のLPNへの帰着は、線形符号の**統計的平滑化（statistical smoothing）**に依存している。これらの手法は、生成行列の行のランダムな疎な組み合わせが、統計的に一様分布に近いことを要求する。この要件は、結果として得られる平均ケースの困難性を、ノイズ率が $1/2 - 1/\text{poly}(n)$ という極めて高い範囲に限定してしまう。このような高いノイズ率は、公開鍵アプリケーションには不十分である。公開鍵アプリケーションでは、通常、$n^{-1/2}$ のような逆多項式ノイズ率や、劣指数時間アルゴリズムに対する定数ノイズ率が必要とされる。さらに、これらの既存の帰着で必要とされる最悪ケースの仮定（非常に低いノイズ率における最近傍符号問題の困難性など）は、弱いものであるか、あるいは非現実的な前処理の仮定を必要とする。

手法

著者らは、統計的平滑化の要件を**計算量的不可識別性（computational indistinguishability）**へと緩和する新しいアプローチを提案している。ランダムな符号の行の疎な組み合わせが統計的に一様分布に近いことを求める代わりに、著者らは、それらが一様分布と計算量的に区別不能であることを要求する。

この転換は、与えられた行列 $A \in \mathbb{F}_2^{m \times n}$ の特性に基づいた「ウィン・ウィン（win-win）」構造をもたらす：

1. 符号の復号（Decoding the Code）: ランダムな組み合わせが計算量的に一様分布と区別不能である場合、効率的なLPNソルバーを利用して、行列 $A$ によって生成される符号をランダムノイズから復号できる。
2. 双対の識別（Distinguishing the Dual）: もしランダムな組み合わせが一様分布と計算量的に区別可能であるならば、その識別器は、双対符号の復号問題の決定版（具体的には、固定重みのシンドロームと一様分布の識別）を解くことになる。

この帰着は、もし $A$ が生成行列として見なされるならば、$A^T$ は双対符号のパリティ検査行列として機能するという観察に基づいている。$r^T A$ が与えられたときにベクトル $r$ を復元することは、$r$ をノイズベクトルとする双対符号の復号に相当する。

主な貢献と結果

1. 主要な帰着定理

本論文は、LPNの困難性が以下の2つの問題の**最悪ケース同時困難性（worst-case simultaneous hardness）**から導かれることを示す帰着（定理3.1）を提示している：

• 行列 $A$ によって生成される符号をランダムノイズから復号すること。
• $A$ の双対符号のランダムなノイズ付き符号語（シンドローム）を、一様分布から識別すること。

定理 1.1 (簡略版): $n$ 変数、$t$ サンプル、ノイズ率 $n^{-\alpha}$ を持つ Search LPN を解く効率的なアルゴリズムが非無視可能なアドバンテージを持つと仮定する。このとき、任意の定数 $\beta > 0$（ただし $\alpha + \beta < 1$）に対して、任意の行列 $A$ について以下のいずれかが成立する効率的なアルゴリズム $S$ および $D$ が存在する：

• $S$ は、ノイズ率 $n^{-(\alpha+\beta)}$ のランダムノイズから $A$ によって生成される符号を復号できる。
• または、$D$ は、ノイズ率 $n^{\beta}/m$ において、双対符号のノイズ付き符号語を一様分布から識別できる。

2. 公開鍵暗号への適用

特定のパラメータを設定することで、著者らは、自らの帰着が Alekhnovich の公開鍵暗号構成 [Ale03] で要求される領域において LPN の困難性をもたらすことを示している。

• パラメータ: $\alpha = 0.5$（目標ノイズ率 $n^{-0.5}$）、$\beta = 0.45$、$m = O(n^{2.9})$ と設定する。
• 結果: これは、コードとその双対の同時最悪ケースの困難性を仮定することで、サンプル数 $t=2n$、ノイズ率 $n^{-0.5}$ におけるLPNの困難性を意味する。
• 意義: このパラメータ領域は、統計的平滑化を用いた最悪ケースからの帰着ではこれまで到達不可能であった。

3. 技術的課題と解決策

著者らは、統計的平滑化から計算量的平滑化へと移行する際の困難に対処している。統計的な設定では、フーリエ解析を用いることで、平滑化された行列とノイズの結合分布を容易に扱うことができる。計算的な設定においては、たとえ $r^T A$ が擬似ランダムであっても、漏洩した $r^T e$ が結合分布を区別可能にする可能性があることを著者らは指摘している。

• 解決策: 帰着は、最悪ケースのノイズではなく、ランダムなベルヌーイノイズから復号するアルゴリズム $S$ を構築する。著者らは、ほとんどの平滑化ベクトル $r$ の選択において、ビット $r^T e$ は $r$ を固定した後でも独立なベルヌーイ変数として振る舞うことを証明している。これにより、すべての最悪ケースのエラーベクトルに対して $r^T e$ が偏りを持たないことを要求する必要がなくなり、以前の障壁となっていた条件を回避して帰着を進めることが可能となった。

意義と主張

本論文は、最悪ケースの仮定に基づいて、逆多項式ノイズ率（具体的には $n^{-1/2}$）におけるLPNの平均ケースの困難性を確立するための経路を提供すると主張している。これは、LWEと比較して困難であった、最悪ケースの困難性から公開鍵暗号を構築するという目標に向けた重要な一歩である。

著者らは、以下の制限事項と控えめな主張を明記している：

• 非標準的な仮定: この帰着は、あるコードとその双対の復号の同時困難性に依存している。この仮定は非標準的であり、独立して研究されていない。著者らは、この仮定が既存の仮定よりも弱いと主張しているのではなく、統計的平滑化の障壁を回避するために、彼らの特定のアプローチにとって必要な条件であると述べている。
• ランダム vs 最悪ケースのノイズ: 得られる復号器 $S$ はランダムなベルヌーイノイズに対して機能するが、以前の帰着（例：[BLVW19]）は最悪ケースの有界重みノイズに対する復号器を生成していた。著者らは、彼らのアプローチを最悪ケースのノイズへと拡張することは結果を大幅に強化することになるが、それには計算論的エントロピーを推論するための新しいツールが必要になると認めている。
• 劣指数時間: 定理で指定された最悪ケースの問題（一般的なコードとその双対の復号）に対する最良のアルゴリズムは、劣指数時間で動作する。したがって、この帰着は、劣指数時間の最悪ケースの困難性仮定に基づき、多項式時間アルゴリズムに対するLPNの困難性を確立するものである。

要約すると、本論文は、統計的な平滑化の要件を計算的なものへと交換することで、「クリーンなウィン・ウィン」の帰着を提供しており、コードとその双対の同時困難性を許容するならば、公開鍵暗号に十分なノイズ率におけるLPNの困難性を実現している。