格问题与零知识证明：NTRU与对称布尔函数的探索

### 格问题与零知识证明：NTRU 与对称布尔函数的探索 #### 格问题中的 NTRU 参考点 在格问题的研究中，确定算法中乘积长度以保证 Gram 矩阵元素具有合适大小是一个关键问题。目前，关于格对 LLL 和 BKZ 算法的安全性，尽管有许多不同的建议，但尚未达成普遍共识，这反映了该问题的复杂性。 NTRU 格是一种被提出具有特定比特强度的格。NTRU 矩阵具有如下形式： \[ \begin{pmatrix} I_{n/2} & X \\ 0 & qI_{n/2} \end{pmatrix} \] 其中 \(n\) 为偶数，\(q\) 是大于 1 的整数，\(X\) 是从特定分布中随机选取的整数矩阵，形式如下： \[ X = \begin{pmatrix} x_1 & x_2 & x_3 & \cdots & x_{n/2 - 1} & x_{n/2} \\ x_2 & x_3 & x_4 & \cdots & x_{n/2} & x_1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ x_{n/2} & x_1 & x_2 & \cdots & x_{n/2 - 2} & x_{n/2 - 1} \end{pmatrix}, |x_j| \leq \frac{q}{2} \] NTRU 矩阵的行张成一个“NTRU 格” \(\Lambda \subset R^n\)。在相关研究中，对于 NTRU 给出了如下参数对应的量子比特安全性估计： | \(q\) | \(n = dim(\Lambda)\) | 估计的量子安全性（比特） | | ---- | ---- | ---- | | 2048 | 886 | 128 | | 2048 | 1486 | 256 | 虽然这些估计与我们研究的格基没有直接关联，因为它们具有不同的行列式和结构，但它们与一般预期一致，即维度为 500 或更高（尤其是 1000 或更高）的格问题在密码学上变得困难。 在实验中，长度 \(\ell\) 的选择是这样确定的：NTRU 矩阵行的向量长度，前 \(n/2\) 行大约为 \(\sqrt{\frac{n}{2}}q^2\)，后 \(n/2\) 行恰好为 \(q\)。我们选择足够大的 \(\ell\)，使得结果乘积具有可比的行长度，并确保使用至少与构建 NTRU 格相同数量的随机比特（即 \(n^2 \log_2(q)\)）。 #### 零知识证明在对称布尔函数中的应用 零知识证明（ZKP）是现代密码学的基本概念，也是众多隐私保护构造的重要组成部分。近年来，通用陈述的 ZKP 设计发展迅速，但在许多应用场景中，不仅输入 \(x\) 而且底层函数 \(f\) 都需要保密，而设计这种情况下的 ZKP 问题尚未得到足够关注。 本文针对对称布尔函数类解决了上述问题。对称布尔函数 \(f\) 的输出值仅由 \(n\) 位输入 \(x\) 的汉明重量决定。尽管这个函数类看似受限，但它具有指数级的基数 \(2^{n + 1}\)，并涵盖了许多常见的布尔函数，如阈值函数、排序函数和计数函数等。 具体来说，对于在学习奇偶性带噪声（LPN）假设下安全的承诺方案，我们展示了如何在零知识的情况下证明对于已承诺的对称函数 \(f\)、已承诺的输入 \(x\) 和比特 \(b\)，有 \(f(x) = b\)。该协议的安全性基于一个辅助承诺方案，该方案可以在量子抗性假设（包括 LPN）下实例化。协议还实现了合理的通信成本，具有 \(2^{-\lambda}\) 稳健性误差的变体证明大小为 \(c \cdot \lambda \cdot n\) 比特