47、同态秘密共享与模糊公钥加密技术解析

同态秘密共享与模糊公钥加密技术解析

生成器优化

对于基于DDH的协议，已有研究证明了一些实用的性能改进方法。例如，利用二次互反定理选择伪梅森素数 $p$，使得整数 2 能生成 $Z_p^×$ 的大素数阶子群，从而显著提升DDLog的速度。然而，这些技术在Paillier加密方案中效果不佳，因为在Paillier中，以 2 为生成元的类似子群自然包含在 $n$ 次幂子群中，而非 $\langle 1 + n\rangle$。

虽然通过拒绝采样安全素数直到 $\langle 2\rangle = \langle 1 + n\rangle$ 是可行的，并且使模数 $n$ 接近 2 的幂，但这对安全性的影响尚不明确。不过，对于阶为 $n$ 的子群的“标准”生成元 $(1 + n)$，存在一个小的优化方法：
设 $h$ 为某一方的份额，将其输入到DDLog中。首先，将 $h$ 表示为 $h = an + b$，其中 $a, b < n$。然后可以发现 $h(1 + n) \equiv (a + b)n + b \mod n^2$。由于对应DDLog调用的两个输入在 $\langle 1 + n\rangle$ 的同一陪集中，每个份额的 $b$ 值也相同。因此，不仅可以将伪随机函数 $\varphi$ 的定义域定义为 $Z_n$，更重要的是，可以用 $Z_n$ 中两个值的简单加法替代模 $n^2$ 下与 $(1 + n)$ 的乘法（只需跟踪每一步的 $(a + b) \mod n$）。由于群乘法是DDLog中最耗时的部分，这种优化可以显著节省计算量。

以下是优化步骤的总结：
1. 输入某一方的份额 $h$。
2. 计算 $h = an + b$，其中 $a