PPAD与LWE及迭代平方问题的难度关联解析

# PPAD 与 LWE 及迭代平方问题的难度关联解析 ## 1. 引言 在密码学和计算复杂性领域，PPAD 问题的难度研究一直是一个重要课题。近期的研究表明，PPAD 问题的难度与学习与错误（LWE）假设以及迭代平方（IS）问题紧密相关。本文将深入探讨迭代平方问题在陷门群中的应用，以及如何构建与之相关的非交互论证系统，进而证明 PPAD 问题的难度。 ## 2. 相关理论基础 ### 2.1 推论 1 在定理 7 的假设基础上，额外假设存在一个哈希族 H，对于以下关系 R 具有相关性难解性： \[ R(n)_{\text{State,NextMsg}} := \left\{ \left( \alpha = (n, \tilde{x}'_1, \tilde{y}'_1, \ldots, \tilde{x}'_{dk}, \tilde{y}'_{dk}), r \right) : \begin{array}{l} \tilde{y}'_j \neq f_{n - 1}(\tilde{x}'_j) \text{ 对于某些 } j \\ \text{且 } \tilde{y}''_i = f_{n - 1}(\tilde{x}''_i) \text{ 对于所有 } i \end{array} \right\} \] 其中 \(\{(\tilde{x}''_i, \tilde{y}''_i)\}_{i \in [1,k]}\) 是 B 在输入 \(\{(\tilde{x}'_j, \tilde{y}'_j)\}_{j \in [1,dk]}\) 和随机硬币 r 时的输出。在此条件下，存在一个具有自适应无歧义可靠性的非交互论证系统用于 \(L^k_{f_n}\)。 ### 2.2 大纲 - 批处理协议的实例化 大纲 - 批处理协议（定理 7 和推论 1）的适当实例化可以恢复以下工作中构建的交互式证明系统或非交互论证系统： 1. **#SAT 的交互式证明系统**：[44] 中的 #SAT 交互式证明系统及其 Fiat - Shamir 实例化 [15,39]。求和检查协议可视为以下两个步骤的组合： - 一个 (d + 1) - 查询向下自约简，将关于 d 次 n 元多项式 p（在某个有限域上）的和 \(\sum_{x_1,\ldots,x_n \in \{0,1\}} p(x_1, \ldots, x_n)\) 的陈述约简为 d + 1 个形式为 \(\sum_{x_2,\ldots,x_n} p(\alpha, x_2, \ldots, x_n)\) 的陈述（对于硬编码的 \(\alpha\) 值）。 - 一个 (d + 1) 到 1 的批处理约简，将这些 (d + 1) 个陈述约简为一个关于 \(\sum_{x_2,\ldots,x_n} p(r, x_2, \ldots, x_n)\) 的单一陈述，其中 r 是均匀随机的。 2. **IS 在带符号二次剩余群 \(QR^+_N\) 上的交互式证明系统**：[16,51] 中的 IS 交互式证明系统及其在标准模型中的 Fiat - Shamir 实例化 [43]。令 \(x \xrightarrow{T} y\) 表示陈述 “\(x^{2^T}\) 在 \(QR^+_N\) 上等于 y”。这些协议包括一个 2 - 查询向下自约简，将陈述 \(x \xrightarrow{T} y\) 约简为两个形式为 \(x_i \xrightarrow{T/2} y_i\) 的陈述，以及一个 2 到 1 的批处理约简，使用随机线性组合将这两个陈述组合为一个单一陈述。 3. **适应 \(QR^+_N\) 的连续 VDF**：[23] 中的连续 VDF 协议包括一个 d - 查询向下自约简，将陈述 \(x \xrightarrow{T} y\) 约简为 d 个形式为 \(x_i \xrightarrow{T/d} y_i\) 的陈述，以及一个 d 到 1 的批处理约简，再次使用随机线性组合将这些 d 个陈述约简为一个单一陈述。参数 d 在其构造中设置为 \(O(\lambda)\)，其中 \(\lambda\) 是安全参数。 4. **IS 的交互式证明系统**：[5] 中的 IS 交互式证明系统，在后续部分将详细描述该协议如何适应 “大纲 - 批处理” 框架，并展示如何在标准模型中实例化 Fiat - Shamir 启发式方法。 ### 2.3 大纲 - 批处理协议实例化总结 | 实例化类型 | 问题描述 | 向下自约简 | 批处理约简 | | --- | --- | --- | --- | | #SAT | 计算 d 次 n 元多项式的和 | (d + 1) - 查询 | (d + 1) 到 1 | | IS 在 \(QR^+_N\) 上 | \(x^{2^T}\) 在 \(QR^+_N\) 上等于 y | 2 - 查询 | 2 到 1 | | 连续 VDF | 适应 \(QR^+_N\) 的连续 VDF | d - 查询 | d 到 1 | | IS | 一般的迭代平方问题 | 2 - 查询 | 2λ 到 λ | ## 3. 迭代平方问题 ### 3.1 模 N 的迭代平方问题 #### 3.1.1 定义 迭代平方（IS）问题的定义如下： - **实例**： - 整数 \(N, T \in \mathbb{N}\) - 群元素 \(g \in \mathbb{Z}^*_N\) - **解**：\(f(N, g, T) := g^{2^T} \bmod N\) #### 3.1.2 假设 - **顺序难度假设（假设 8）**：对于安全参数 \(\lambda \in \mathbb{N}\)，令 \(\lambda_{\text{RSA}} \in \lambda^{O(1)}\) 表示对应于 \(\lambda\) 位安全的 RSA 模数的大小。采样 \(N = pq\) 作为两个随机 \(\lambda_{\text{RSA}}/2\) 位素数的乘积，以及 \(g \leftarrow \mathbb{Z}^*_N\)。考虑任何时间参数 \(T = 2^{o(\lambda)}\)。任何使用 \(2^{o(\lambda)}\) 并行度并以在 \(\lambda\) 中不可忽略的概率计算 \(f(N, g, T)\) 的算法 \(A\)，需要顺序时间 \(T(1 - o(1))\) 次群运算。 - **标准难度假设（假设 9）**：对于安全参数 \(\lambda \in \mathbb{N}\)，令 \(N\) 和 \(g\) 如假设 8 中采样。存在一个有效可计算的函数 \(T(1^\lambda)\)，使得没有 \(\lambda^{O(1)}\) 时间的算法能够以不可忽略的概率计算 \(f(N, g, T)\)。 ### 3.2 未知阶的陷门群 #### 3.2.1 未知阶群的定义 未知阶群的采样器由以下两个功能组成： - **设置算法 \(Setup(1^\lambda)\)**：采样一个阶至多为 \(2^\lambda\) 的群 \(G_\lambda\) 的描述。对于我们的目的，群描述包括一个特殊的单位元素 \(id_G\) 和一个有效的成员测试算法，该算法以任意字符串为输入，决定该字符串是否为 \(G_\lambda\) 的有效元素。 - **有效算法**：给定 \(G_\lambda\) 的描述，有以下多项式时间算法： - 采样一个均匀随机的群元素。 - 计算群运算 \((g, h) \mapsto gh \in G_\lambda\)。 - 计算逆映射 \(g \mapsto g^{-1} \in G_\lambda\)。 这些有效群运算通常意味着可以通过重复平方在时间 \(poly(\lambda) \cdot \log(x)\) 内计算幂运算 \(g \mapsto g^x\)。例如，这意味着可以在时间 \(T \cdot poly(\lambda)\)（或 \(T\) 次群运算）内计算 \(g \mapsto g^{2^T}\)。 #### 3.2.2 相关假设 - **\((T, p)\) - 顺序难度假设（假设 10）**：给定 \(G_\lambda\) 的描述和一个随机群元素 \(g\)，任何以顺序时间 \(T(1 - o(1))\) 运行且具有 \(p(