A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System
Paillier 的概率性公钥系统的概括、简化和一些应用
我们提出了对 Paillier 的概率公钥系统的概括，在这个系统中，扩展因子被降低，即使在公钥被固定后，也可以调整方案的块长，而不会失去同态特性。我们表明，这个概括与 Paillier 的原始系统一样安全。我们构建了一个广义方案的阈值变体，以及零知识协议，以表明一个给定的密码文本加密了一组给定的明文中的一个，以及验证明文的乘法关系的协议。
然后，我们展示了这些构件如何用于将该方案应用于高效的电子投票。与之前最知名的方案相比，这大大减少了计算选举的最终结果所需的工作。我们展示了是否投票的基本方案如何可以很容易地适应于为
1 介绍
在 [9] 中，Paillier 提出了一个新的概率加密方案，该方案基于群
我们提出了一个通用系统的阈值变体，允许一些服务器共享秘钥的知识，这样他们中任何一个足够大的子集都可以解密一个密码文本，而较小的子集则没有有用的信息。我们在随机神谕模型中证明，该方案与标准的集中式实现一样安全。
我们还提出了一个零知识证明，允许验证者证明一个给定的密码文本编码一个给定的明文。由此，我们推导出其他工具，如显示一个密码文本编码若干个给定明文中的一个的协议。最后，我们提出一个协议，允许验证加密值之间的乘法关系而不透露额外的信息。
我们看一下这在电子投票方案中的应用。已知有大量的此类方案，但最有效的方案，至少在投票者所需的工作方面，是由 Cramer、Gennaro 和 Schoenmakers [4] 提出的。该协议实际上提供了一个通用框架，允许使用任何概率加密方案来加密投票，如果该加密方案具有一系列 "不错" 的属性，特别是它必须是同构的。这方面的基本想法很简单：每个投票者都会广播他的投票加密（通过将其发送到公告板），并证明该投票是有效的。然后，所有有效的投票被组合起来，利用加密方案的同态性，产生一个结果的加密。最后，一组受托人（他们以门槛方式分享方案的秘密密钥）可以解密并公布结果。
Paillier 在 [9] 中已经指出，由于他的加密方案是同态的，所以可能适用于电子投票。然而，为了在 [4] 的框架内应用它，还缺少一些重要的构件：我们需要一个有效的投票有效性证明，以及该方案的有效阈值变体，以便在不允许单个实体了解单个选民如何投票的情况下解密结果。
这些积木正是我们在这里提供的。因此，我们立即得到一个投票协议。在这个协议中，投票者需要做的工作与 [4] 中的原始版本相同。然而，正如我们现在所解释的，产生结果所需的工作却大大减少。在 [4] 中使用的
在我们下面提出的方案中，这项工作可以被完全去除。我们的解密过程直接产生所需的结果。我们还给出了有效实现实际选举中出现的投票限制的方法，例如允许在
2 相关工作
在独立于我们的工作，但比我们更早的工作中，Fouque, Poupard 和 Stern [6] 提出了 Paillier 原始方案的第一个阈值版本。像我们的阈值方案一样，[6] 使用了 Shoup 的阈值
Baudron, Fouque, Pointcheval, Poupard 和 Stern [1] 在与我们同时进行的独立工作中，提出了一个与我们有点类似的投票方案。他们的工作可以被看作是对我们工作的补充，因为他们的建议更倾向于大规模选举的系统架构方面，而不太倾向于对构件的优化。为了与他们的方案相比较，我们首先注意到，在那里，模数长度
因为我们的投票方案使用广义的 Paillier 密码系统，所以
在 [8] 中，Hirt 和 Sako 提出了一种建立无收据选举方案的一般方法，即由于选民不能向他人证明他们是如何投票的，所以不可能出现买票或强迫投票的协议。他们的方法可以应用于制作 [4] 方案的无收据版本。它也可以应用于我们的方案，与无收据情况下的效率增益相同。