抗选择密文攻击的门限密码系统与不经意多项式评估

### 抗选择密文攻击的阈值密码系统与不经意多项式求值 #### 抗选择密文攻击阈值密码系统相关内容 在密码学领域，保障加密系统在面对选择密文攻击时的安全性至关重要。下面将详细介绍相关的证明系统以及Paillier密码系统的多种版本。 ##### 证明系统的健全性与模拟健全性 在证明系统中，存在这样的情况：当机器以一定概率 $\nu' \geq 1/9$ 进行重放时，会输出关于错误单词 $(pk_0, pk_1, a_0, a_1)$ 的两个可接受证明。假设攻击者未破坏哈希函数 $H$ 的抗碰撞性，通过一系列等式推导，最终能得出 $M_0 = M_1$，这意味着该单词属于相应语言。 在随机预言机假设下，根据生日悖论，要以大于 1/9 的概率找到碰撞，需要向 $H$ 进行超过 $\sqrt{q}/3$ 次查询。由此可得出不等式： $\frac{16qht}{\nu} \geq t' \geq \frac{\sqrt{q}}{3} \tau$ 其中，$\tau$ 是评估 $H$ 所需的时间。进而得到： $Succ_{sim - nizk}(t) \leq \nu \leq \frac{48qh}{\sqrt{q}t}\tau$ 这证明了证明系统的健全性，并且即使对于拥有辅助信息的攻击者，该引理依然成立，从而进一步证明了模拟健全性。 ##### Paillier密码系统 - **基本密码系统回顾**：Paillier密码系统基于 Carmichael lambda 函数在 $Z_{n^2}^*$ 中的性质。主要有两个性质：对于任意 $w \in Z_{n^2}^*$，有 $w^{\lambda(n)} = 1 \mod n$ 和 $w^{n\lambda(n)} = 1 \mod n^2$。 - 密钥生成：选择 RSA 模数 $n = pq$（$p$ 和 $q$ 为素数），整数 $g$ 满足其阶为 $n\alpha$ 模 $n^2$。公钥为 $pk = (n, g)$，私钥为 $sk = \lambda(n)$。 - 加密过程：要加密消息 $M \in Z_n$，随机选择 $x \in Z_n^*$，计算密文 $c = g^M x^n \mod n^2$。 - 解密过程：解密时，计算 $M = \frac{L(c^{\lambda(n)} \mod n^2)}{L(g^{\lambda(n)} \mod n^2)} \mod n$，其中 $L$ 函数对集合 $U_n = \{u < n^2 | u = 1 \mod n\}$ 中的元素进行操作，$L(u) = \frac{u - 1}{n}$。其语义安全性基于区分模 $n^2$ 的 $n$ 次剩余的难度。 - **IND - CPA 阈值版本**： - 密钥生成算法：选择两个安全素数 $p = 2p' + 1$ 和 $q = 2q' + 1$ 的乘积 $n$，使得 $\gcd(n, \varphi(n)) = 1$。私钥 $sk = \beta \times m$（$m = p'q'$，$\beta$ 是 $Z_n^*$ 中的随机元素）通过 Shamir 方案在 $mn$ 上进行共享。选择一个能以压倒性概率生成 $Z_{n^2}^*$ 中平方循环群的平方 $v$，验证密钥 $vk_i$ 通过公式 $v^{\Delta sk_i} \mod n^2$ 获得，其中 $\Delta = \ell!$，$\ell$ 是服务器数量。 - 加密算法：加密消息 $M$ 时，随机选择 $x \in Z_n^*$，计算 $c = g^M x^n \mod n^2$。 - 部分解密算法：第 $i$ 个玩家 $P_i$ 使用其秘密份额 $sk_i$ 计算解密份额 $c_i = c^{2\Delta sk_i} \mod n^2$，并进行正确解密的证明，确保 $c^{4\Delta} \mod n^2$ 和 $v^{\Delta} \mod n^2$ 被提升到相同的幂次 $sk_i$ 以得到 $c_i^2$ 和 $vk_i$。 - 恢复算法：若少于 $t + 1$ 个解密份额有有效的正确性证明，算法失败；否则，选择 $t + 1$ 个有效份额的集合 $S$，通过拉格朗日插值计算明文。 - **IND - CCA 阈值版本**： - 密钥生成算法：对于 $j = 0, 1$，选择两个安全素数 $