该论文研究了带噪奇偶学习（LPN）问题的困难性。LPN 是密码学中的基础假设，支持从对称密钥原语到公钥加密等多种构造。一个核心开放问题是：LPN 的平均情况困难性能否像 LWE 那样基于最坏情况复杂性假设。现有的最坏情况到平均情况归约（BLVW19, YZ21）依赖于线性码的统计平滑，这导致平均情况困难性仅限于噪声率高达 1/2 - 1/poly(n) 的参数，不足以用于公钥应用。本文探索了一种新方法：不要求生成矩阵的随机稀疏行组合在统计上接近均匀分布，而只要求它们在计算上不可区分。这产生了一个清晰的赢-赢结构：任何高效的 LPN 求解器都可以转化为两个高效算法 (S, D)，使得对于任意适当维度的矩阵 A 在 F2 上，要么 S 解码由 A 生成的码从随机噪声中，要么 D 区分该码的对偶的随机噪声码字与均匀分布。通过用适当的参数实例化该归约，论文获得了逆多项式噪声率 n^{-α}（α<1 任意常数）下 LPN 的平均情况困难性，假设最坏情况下同时困难性：从随机噪声中解码一个码，以及区分其对偶的随机噪声码字与均匀分布。特别地，当 α=1/2 时，归约得到了 Alekhnovich 公钥加密构造所需参数区间的 LPN 困难性，这一区间以前无法通过最坏情况归约达到。