PPAD与LWE及迭代平方问题的难度等价性解析

### PPAD与LWE及迭代平方问题的难度等价性解析 在计算复杂性理论的研究中，PPAD（Polynomial Parity Argument, Directed）问题的难度一直是一个备受关注的话题。本文将深入探讨PPAD与学习误差问题（LWE）以及迭代平方问题（Iterated Squaring）之间的关系，揭示PPAD问题的难度与这些问题的紧密联系。 #### 1. 模运算与迭代平方问题的挑战及解决方案 在处理迭代平方问题时，直接使用均匀随机模数N并不是一个好的选择。根据素数定理，N有逆多项式概率是素数，此时群阶φ(N) = N - 1可以被高效计算，使得模N的平方问题并不困难。为了解决这个问题，我们考虑选择N = N1·...·Npoly(λ)，其中所有整数Ni都是公开的，并且在范围[1, 2λ]内均匀随机选取。 我们构建困难PPAD实例的技术同样适用于这种模数的选择。只需要有一种方法能够高效地采样平方问题的描述，同时包含群阶|Z×N| = φ(N)的陷门即可。这可以通过高效的随机因式分解整数算法来实现。 从理论上来说，PPAD中的公共硬币难度可以从LWE的难度以及模N的迭代平方问题（IS）的多项式难度推导得出。为了完成证明，我们还需要进一步说明这可以从RSA模数下（秘密硬币）IS的多项式难度推导而来。通过直接归约，我们将RSA模数IS问题实例嵌入到这个新的IS问题的公共硬币实例中。关键在于，除了极小的概率外，在N1, ..., Npoly(λ)中至少有一个Ni是RSA模数。 #### 2. 预备知识 在深入研究之前，我们需要了解一些基本的符号和定义。 ##### 2.1 符号说明 以下是本文中使用的一些符号： 1. 对于a, b ∈ N，且a < b，[a, b]表示整数序列{a, a + 1, ..., b}。 2. 对于字母表Σ和n ∈ N，Σn、Σ<n和Σ≤n分别表示长度等于、小于和小于等于n的Σ上的字符串。ε表示空字符串，ab表示字符串a和b的连接。 3. 向量和元组用粗体表示。向量或元组x ∈ X k被解析为x =: (x0, ..., xk - 1)，称为k - 向量。带下标向量xv ∈ X k被解析为xv =: (xv,0, ..., xv,k - 1)。 4. 对于x ∈ X，y ∈ Y和函数f : X → Y，x f−→ y表示“y等于f(x)”这个陈述。在上下文明确时，我们会简化符号，例如对于h := g2T mod N，我们简记为g T−→ h。这个符号也可以扩展到向量，对于x ∈ X k和y ∈ Yk，f = f k : X k → Yk定义为(f(x0), ..., f(xk - 1))，x f−→ y表示对于所有i ∈ [0, k - 1]，xi f−→ yi。 5. 对于陈述x，π(x)表示x的非交互式证明。例如，对于x, y和f，π(x f−→ y)表示陈述x f−→ y的非交互式证明。 6. 对于x ∈ X和y ∈ Y，y := A(x)（或y ← A(x)）表示确定性（或随机化）算法A在输入x上执行并输出y。对于k ∈ N，向量x ∈ X k和y ∈ Yk，y := A(x)表示A对每个xi进行重复并行执行，即yi := A(xi)，对于所有i ∈ [0, k - 1]。 ##### 2.2 搜索问题、TFNP及归约 我们定义了搜索问题以及相关的复杂度类： - **搜索问题**：搜索问题是一个关系R ⊆ {0, 1}∗× {0, 1}∗。R(x)表示{y : (x, y) ∈ R}。函数f : {0, 1}∗→ {0, 1}∗∪{⊥}被称为解决R，如果对于每个满足R(x) ≠ ∅的x ∈ {0, 1}∗，有f(x) ∈ R(x)；对于其他x，f(x) = ⊥。 - **总关系**：关系R被称为总关系，如果对于所有x ∈ {0, 1}∗，存在y使得(x, y) ∈ R。 - **多项式平衡**：关系R被称为多项式平衡，如果存在多项式p，使得对于任何字符串x, y ∈ {0, 1}∗，如果(x, y) ∈ R，则|y| ≤ p(|x|)。 - **FNP**：复杂度类FNP由所有多项式平衡的搜索问题R组成，对于这些问题，存在一个多项式时间算法，在输入(x, y)时输出(x, y)是否属于R。 - **TFNP**：复杂度类TFNP由FNP中的所有总搜索问题组成。 对于搜索问题P和Q，从P到Q的随机Karp归约（误差为ϵ(·)）是一对概率多项式时间（p.p.t.）机器(M, N)，使得如果f是解决Q的函数，那么对于任何x ∈ {0, 1}n且P(x) ≠ ∅，当采样x′ ← M(x)，y ← N(f(x′))时，有Pr[(x, y) ∈ P] ≥ 1 - ϵ(n)。 我们还考虑了松弛可验证线的汇点问题（RelaxedSinkOfVerifiableLine，RSVL），它与本文的主要结果相关。RSVL不是一个总问题，因为无法从语法上保证后继和验证电路的行为良好。 RSVL的定义如下： - **实例**： 1. 布尔电路S : {0, 1}m → {0, 1}m 2. 布尔电路V : {0, 1}m × [0, 2m - 1] → {accept, reject} 3. 整数L ∈ [0, 2m - 1] 4. 字符串v0 ∈ {0, 1}m - **承诺**：对于每个v ∈ {0, 1}m和i ∈ [0, 2m - 1]，如果i ≤ L且v = Si(v0)，则V(v, i) = 1。 - **解决方案**：以下之一： 1. 汇点：一个顶点v ∈ {0, 1}m，使得V(v, L) = 1。 2. 假阳性：一对(v, i) ∈ {0, 1}m × [0, 2m - 1]，使得v ≠ Si(v0)且V(v, i) = 1。 虽然RSVL可能不在FNP中，更不用说在PPAD中，但已有研究构建了从RSVL到EOML（CLS ⊆ PPAD的一个完全搜索问题）的随机归约，误差为1 - n−O(1)。这个归约足以基于RSVL的类似难度来建立EOML的标准密码学难度。 ##### 2.3 学习误差问题（LWE） LWE问题是密码学中的一个重要问题。对于任何s ∈ Znq和任何分布χ ⊆ Zq，LWE分布As,χ ∈ Znq × Zq通过均匀随机选择a ∈ Znq，采样e ← χ，并输出(a, b = ⟨s, a⟩ + e)来采样。 决策LWE假设：设m = m(n) ≥ 1，q = q(n) ≥ 2是整数，χ(n)是Zq(n)上的概率分布。参数化的LWEn,m,q,χ问题是区分m(n)个独立样本是从As,χ（其中s是均匀随机采样的）中抽取的，还是从均匀分布中抽取的。该假设认为，对于多项式规模的对手来说，决定LWEn,m,q,χ问题是困难的。 ##### 2.4 相关不可陷哈希族 哈希族H = {Hλ : {0, 1}s(λ)×{0, 1}n(λ) → {0, 1}m(λ)}λ∈N是一组带密钥的哈希