Paillier NIZK 同态非交互零知识证明

NIZKProof 与 NIZKVerify

是的，这两行代码确实是互为反向运算。让我们详细解释一下它们是如何互为反向运算的。

生成证明 (NIZKProof)

在 NIZKProof 函数中，我们生成了证明值 sigma，具体步骤如下：

sigma := new(big.Int).Exp(rho, NInv, N)

这行代码的含义是：

• rho 是一个随机数。
• NInv 是 N 在 phiN 模下的逆元。
• sigma 是 rho 的 NInv 次幂，模 N。

简而言之，sigma 是通过对 rho 进行 NInv 次幂运算得到的。

验证证明 (NIZKVerify)

在 NIZKVerify 函数中，我们需要验证 sigma 是否正确。具体步骤如下：

tmp := new(big.Int).Exp(new(big.Int).SetBytes(sigma), N, N)

这行代码的含义是：

• sigma 是之前生成的证明值。
• N 是模数。
• tmp 是 sigma 的 N 次幂，模 N。

互为反向运算

让我们看看这两步运算是如何互为反向运算的：

1. 生成 sigma：

   sigma := new(big.Int).Exp(rho, NInv, N)
   • sigma = rho^NInv (mod N)

2. 验证 sigma：

   tmp := new(big.Int).Exp(new(big.Int).SetBytes(sigma), N, N)
   • tmp = sigma^N (mod N)
   • 将 sigma 代入：tmp = (rho^NInv)^N (mod N)

根据模运算的性质，(rho^NInv)^N ≡ rho (mod N)，因为 NInv 是 N 在 phiN 模下的逆元，所以 NInv * N ≡ 1 (mod phiN)，这意味着 (rho^NInv)^N ≡ rho (mod N)。

验证逻辑

在验证过程中，我们比较 rho 和 tmp：

if rho.Cmp(tmp) != 0 {
    return false
}

• 如果 sigma 是正确的，即 sigma = rho^NInv (mod N)，那么 sigma^N (mod N) 应该等于 rho。
• 因此，tmp 应该等于 rho，如果不等，则证明无效。

总结

• 生成证明：sigma = rho^NInv (mod N)
• 验证证明：tmp = sigma^N (mod N)，并比较 tmp 和 rho

这两步运算确实是互为反向运算，通过这种方式，我们能够验证 sigma 是否是通过正确的 rho 生成的，从而验证证明的有效性。

latex 证明

好的，让我们用 LaTeX 来表示这些数学表达式。

生成证明 (NIZKProof)

在 NIZKProof 函数中，生成证明值 $\sigma$ 的步骤可以用 LaTeX 表示如下：

$$\sigma = \rho^{N^{-1}} \mod N$$

其中：

• $\rho$ 是一个随机数。
• $N^{-1}$ 是 $N$ 在 $\phi(N)$ 模下的逆元。

验证证明 (NIZKVerify)

在 NIZKVerify 函数中，验证 $\sigma$ 的步骤可以用 LaTeX 表示如下：

$$\text{tmp} = \sigma^N \mod N$$

其中：

• $\sigma$ 是之前生成的证明值。
• $N$ 是模数。

互为反向运算

让我们看看这两步运算是如何互为反向运算的：

1. 生成 $\sigma$：

   $$\sigma = \rho^{N^{-1}} \mod N$$

2. 验证 $\sigma$：

   $$\text{tmp} = \sigma^N \mod N$$

将 $\sigma$ 代入第二个表达式：

$$\text{tmp} = (\rho^{N^{-1}})^N \mod N$$

根据模运算的性质：

$$(\rho^{N^{-1}})^N \equiv \rho \mod N$$

因为 $N^{-1}$ 是 $N$ 在 $\phi(N)$ 模下的逆元，所以 $N^{-1} \cdot N \equiv 1 \mod \phi(N)$，这意味着：

$$(\rho^{N^{-1}})^N \equiv \rho \mod N$$

验证逻辑

在验证过程中，我们比较 $\rho$ 和 $\text{tmp}$：

$$\text{if } \rho \neq \text{tmp} \text{ then return false}$$

• 如果 $\sigma$ 是正确的，即 $\sigma = \rho^{N^{-1}} \mod N$，那么 $\sigma^N \mod N$ 应该等于 $\rho$。
• 因此，$\text{tmp}$ 应该等于 $\rho$，如果不等，则证明无效。

总结

• 生成证明：

  $$\sigma = \rho^{N^{-1}} \mod N$$

• 验证证明：

  $$\text{tmp} = \sigma^N \mod N$$

通过这种方式，我们能够验证 $\sigma$ 是否是通过正确的 $\rho$ 生成的，从而验证证明的有效性。

上面的证明是 Paillier 与 NIZK 结合体

是的，这个证明涉及到 Paillier 同态加密方案与非交互式零知识证明（NIZK）相结合。让我们详细解释一下这两者如何结合在一起。

Paillier 同态加密

Paillier 同态加密方案是一种基于加法同态的公钥加密方案，具有以下特性：

1. 密钥生成：

   • 选择两个大素数 $p$ 和 $q$，计算 $N = pq$。
   • 计算 $\lambda = \text{lcm}(p-1, q-1)$。
   • 选择一个随机数 $g$ 满足 $g \in \mathbb{Z}_{N^2}^*$。
   • 公钥为 $(N, g)$，私钥为 $\lambda$。

2. 加密：

   • 给定消息 $m \in \mathbb{Z}_N$，选择一个随机数 $r \in \mathbb{Z}_N^*$ 。
   • 计算密文 $c = g^m \cdot r^N \mod N^2$。

3. 解密：

   • 给定密文 $c$，计算 $m = L(c^\lambda \mod N^2) \cdot L(g^\lambda \mod N^2)^{-1} \mod N$，其中 $L(x) = \frac{x-1}{N}$。

非交互式零知识证明（NIZK）

非交互式零知识证明是一种证明方法，允许证明者向验证者证明某个陈述是真实的，而不泄露任何额外的信息。通常使用 Fiat-Shamir 启发式将交互式证明转换为非交互式证明。

结合 Paillier 和 NIZK

在结合 Paillier 加密和 NIZK 的场景中，通常需要证明某个加密值满足特定的属性，而不泄露具体的值。例如，证明某个加密值是某个已知值的加密。

假设我们有一个 Paillier 加密的值 $c$，我们希望证明这个密文对应的明文是某个已知值 $m$，而不泄露任何关于 $m$ 的信息。

生成证明

1. 选择一个随机数 $\rho$。
2. 计算 $\sigma = \rho^{N^{-1}} \mod N$，其中 $N^{-1}$ 是 $N$ 在 $\phi(N)$ 模下的逆元。

验证证明

1. 计算 $\text{tmp} = \sigma^N \mod N$。
2. 比较 $\text{tmp}$ 和 $\rho$，如果相等，则证明有效。

数学表达

1. 生成证明：

   $$\sigma = \rho^{N^{-1}} \mod N$$

2. 验证证明：

   $$\text{tmp} = \sigma^N \mod N$$

根据模运算的性质：

$$(\rho^{N^{-1}})^N \equiv \rho \mod N$$

结合的意义

通过这种结合，我们可以在 Paillier 加密的基础上，使用 NIZK 来证明某些关于加密值的属性，而不泄露任何关于这些属性的具体信息。这种方法在密码学协议和隐私保护计算中具有广泛的应用。

总结

• Paillier 同态加密 提供了加密和解密机制。
• NIZK 提供了零知识证明机制。
• 结合这两者，可以在不泄露具体信息的情况下，证明某个加密值满足特定的属性。