补二次同余问题的零知识证明协议

问题

二次同余问题定义如下：对于给定的整数 $x$ 和 $n$，判定是否存在整数 $y$ 使得 $x$ 与 $y$ 在模 $n$ 的意义下相等，即：

\[y^2 \equiv x \pmod{n}\]

或表达如下：

\[y^2 ~\%~ n = x ~\%~ n\]

其中 $\%$ 表示取模运算。

补二次同余问题，即是要求判定不存在这样的 $y$。

补二次同余问题的零知识证明协议，即使要求设计一个零知识证明协议，去证明不存在这样的 $y$。也即，假如证明者可以判定不存在这样的 $y$，则验证者可以在不知道 $y$ 的情况下，验证证明者的判定是否正确。

解法（零知识证明协议）

1. 验证者计算 $x ~\%~ n$，记为 $r$；
2. 验证者随机选取一个整数 $y’$；

3. 验证者从与 $y’^2$ 对 $x$ 同余的数中随机选取一个，记为 $x’$；

   即要求 $x’ ~\%~ n = y’^2 ~\%~ n$。

4. 验证者求解 $x’$ 对 $x$ 的商 $k’$ 和 余数 $r’$；

   即解方程 $x’ = k’ x + r’$，其中 $0 \le r’ \lt x$ 。

5. 验证者计算 $n (k’ x + r’)$（记为 $\alpha$），和 $r (k’ x + r’)$（记为 $\beta$）；

6. 验证者要求证明者判定是否存在整数 $y’’$ 使得 $y’‘^2 \equiv \beta \pmod{\alpha}$；

   即解关于 $\beta$ 和 $\alpha$ 的二次同余问题。

7. 或者，验证者直接选择随机的 $x’$，要求证明者判定同上的二次同余问题；
8. 如果验证者不是随机选取时，证明者以显著更高的概率给出“$y’$ 不存在”的判定，那么验证者可以认为证明者是诚实的；
9. 而且，如果 $y’$ 存在，则验证者不会在此过程中得到任何关于 $y$ 的信息，只会得到“$y$ 存在”这一信息而已。

合理性/健壮性（Soundness）

即证明：如果证明者总能给出“$y’$ 不存在”的判定，那么 $y$ 确实不存在。

使用反证法，假设 $y$ 存在（但未知）：

1. 则存在一个 $k$ ，使得 $y^2 = k n + r$；
2. 而 $y’^2 = k’ x + r’$；

3. 所以 $(y y’)^2 = (k n + r) * (k’ x + r’) = k n (k’ x + r’) + r (k’ x + r’)$；

   看到了吧，上面 $\alpha$ 和 $\beta$ 奇怪的求值式就是从这来的。

4. 所以 $y y’$ 就是 $\alpha = n (k’ x + r’)$ 关于 $\beta = r (k’ x + r’)$ 的二次同余数；
5. 所以存在整数 $y’’ = y y’$ 使得 ${y’’}^2 \equiv \beta \pmod{\alpha}$；
6. 也即，关于 $\alpha$ 和 $\beta$ 的二次同余问题有解。

反之，如果证明者给出“$y’’$ 不存在”的判定：

1. 那么关于 $\alpha$ 和 $\beta$ 的二次同余问题就无解；
2. 那么 $y$ 就不存在，原命题得证。

完备性（Completeness）

即要求证明者不会被误导或欺骗。

1. 假设证明者已知 $x$ 和 $n$；
2. 证明者易知 $x’$，因为 $x’ = \alpha / n = \beta / r$。
3. 假如没有判定“$y$ 不存在”的本事，那么他就要识别出 $x’$ 是不是随机的；
4. 那么他就必须求解是不是有某个 $y’$ 使得 $y’^2 \equiv x’ \pmod{x}$；
5. 但是，上述问题同样是一个二次同余问题，这无异于直接解决“$y$ 是否存在”的原问题；
6. 所以证明者也无法判定“$y’$ 是否存在”。

证毕。

思路和讨论

我有 99% 的信心上述证明是对的，但是不敢肯定，简单说一下我的设计思路。

核心思路就是，我们要从原问题中导出一个新问题，而且：

1. 原问题与新问题的答案上相互关联，即新问题的答案可以导出原问题的答案；

   如上述对 $y’’$ 存在性的判定可以导出 $y$ 的存在性。

2. 新问题本身和原问题是同一类问题，所以解决新问题不会比解决原问题更容易；

   如上述对 $y’’$ 存在性的判定本身就是一个二次同余问题。

3. 从原问题导出新问题的过程本身也利用了原问题！！！

   如上述的 $x’$ 也是很巧妙地通过二次同余问题构造的 —— 这样，如果证明者尝试反推问题，他就会遇到他本来就不会解决的问题，所以他怎么都避不开解决原问题！！！