在日常生活中，我们需要聚集多人的意见来进行群体决策，大到总统选举，小到某地最受喜爱的餐厅排序。这个过程一般通过投票完成，投票的分类的一般有如下几种。

  1. 是/否问题：投票者只能回答是或否
  2. 1-out-L：投票者在L个选项中选一个
  3. K-out-L：投票者从 L个选项中选择K个，K无次序之分。
  4. K-out-of-L order voting：投票者从L个选项中选择K个，并且K有次序之分的。
  5. 1-L-K voting ：投票者先从L集合中选择一个，再从对应的集合中选择K个。
  6. write-in voting：在投票时，可以选择不在候选项中的其他选择。

也可以按照票的权重进行分类：

  1. equal-voting：每个投票者投出的票的权重一样。
  2. weighted-voting：每个投票者投出的票的权重不一样。

在投票系统的设计中，一般存在如下的需求。

  1. 完全性：所有的有效投票都应被正确计算在投票结果内。
  2. 稳固性：不诚实投票者不能对选票进行破坏。
  3. 秘密性：任何选票都应该是保密的，任何人都无法将一张选票和某一投票者联系起来。
  4. 唯一性：只有有资格的人能提交一张合法的选票，不能重复投票。
  5. 合法性：在投票的中间过程，任何人的行为都无法影响投票的结果。
  6. 公正性：投票的中间结果不能泄漏。
  7. 可验证性：任何人无法伪造投票结果。

其中秘密性涉及到了投票者的隐私，在实际研究中关注较多。一般来说，差分隐私和同态加密是两种广泛用于保护用户隐私的工具。

差分隐私的概念最早由 Cynthia Dwork 等人在 2006 年提出。区别以往的ad-hoc 隐私保护方案(比如 k-anonymity, l-diversity, t-closeness)，差分隐私的主要贡献就是提供了个人隐私泄露的数学的定义。差分隐私通过使用随机噪声来确保查询的公开可见信息的结果并不会因为个体的变化而变化。ε-差分隐私具体的定义如下：

给定数据集D和其相邻数据集D'，如果一个隐私算法 f'满足差分隐私，那么对于f'的任意输出C，均满足Pr(f^' (D)=C)≤e^ε Pr(f^' (D')=C)。其中，任意和D最多相差一条记录的数据集D'均为D的相邻数据集。ε表示隐私保护程度，对于给定的数据集和查询函数f，其对应的隐私算法f^'的ε越小，隐私保护程度越高。

差分隐私分为中心化差分隐私和本地化差分隐私。中心化差分隐私技术要求第三方数据收集者可信，且收集到的数据有较高的效用。本地化差分隐私在本地加噪，第三方不需可信的假设，但同时数据的效用较低。

在中心化差分隐私和投票的结合中，数据收集者收集每个投票者的选项，聚集之后对总的选票加入噪声再进行发布。例如[1]提出基于排序的中心化差分隐私算法P-BORDA和P-SORT。其中P-BORDA主要思想是根据Borda count算法为每个投票者的排序的每个选项分配一个得分，数据收集者收集并累加每个选项的的得分，并在每个选项的总得分上增加噪声，最终根据加噪的每个选项的得分得到最终的排序。而P-SORT则是收集每个选项对的偏好并累加，再在累加值上添加噪声，最后根据Kwiksort算法得出最终排序。

针对本地化差分隐私算法，[2]对1-out-L问题进行研究，在每个人的投票上加入噪声，数据收集者收集到的是加噪的选票，并对加噪选票进行聚合得到最终结果。除此之外，这篇文章还考虑了每个人的权重问题，在以往的投票中，给出答案与最终结果相同的投票者具有高投票权重。[3]对加权投票的是否问题进行了研究，考虑了权重数据累加值与预设配额的大小关系。[4]基于P-SORT算法提出本地化差分隐私算法LDP-Kwiksort，如下图。一共对每个投票者发生K次问询，每次问询中抽取一个选项对，投票者回答对该选项对的偏好关系并加噪上传给数据收集者，数据收集者对答案进行分类累加，最后执行Kwiksort算法得到最终排序结果。

同态加密最早是1978年，由Ron Rivest、Leonard Adleman和Michael L德图佐斯提出。它允许对密文进行特定的代数运算后依然能得到加密的结果，将该结果解密以后的结果与对明文进行同样运算的结果会保持一致。应用同态加密的投票流程如下。

投票者对投票用私钥进行加密，发送给计票者进行票数统计。统计结果后发送给Athena进行解密，最终公布结果。此系统把计票方和票数解密方分开来保障投票者的隐私性。在同步态加密投票系统的设计中，同态加密常常与其他技术结合，最常见的是签名同态加密[5]，一步完成对选票的加密和签名，系统流程如下，签名同态加密除了保障系秘密性之外，还可以保障系统的完全性和可验证性。

也有学者将同态加密与区块链进行结合。区块链平台去中心化的特点可以解决传统电子投票系统中心化程度高带来的高风险问题，并剥离了电子投票对中心管理机构的依赖。文献[6]提出每个人都可以利用加密的同态性来验证选票的有效性和计票结果，使得选举结果可以公开核实。

总体来说，差分隐私和同态加密手段对投票系统的应用各有利弊。本地化差分隐私是一种轻量级的技术，可以完全建立在第三方不可信的条件上，但如何提高投票的准确性一直是研究的重点。而针对同态加密来说，投票结果计算准确，但解密方不能与计票者串通，且对于大型投票来说工程较大，实施较为困难。

  • [1] Hay M, Elagina L, Miklau G. Differentially private rank aggregation[C] Proceedings of the 2017 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2017: 669-677.
  • [2] Li Y, Miao C, Su L, et al. An Efficient Two-Layer Mechanism for Privacy-Preserving Truth Discovery [C]. In KDD, 2018: 1705–1714.
  • [3] Yan Z, Liu J, Liu S. DPWeVote: differentially private weighted voting protocol for cloud-based decision-making[J]. Enterprise Information Systems, 2019, 13(2): 236-256.
  • [4] Yan Z, Li G, Liu J. Private rank aggregation under local differential privacy[J]. International Journal of Intelligent Systems, 2020, 35(10): 1492-1519.
  • [5] Fan X, Wu T, Zheng Q, et al. HSE-Voting: A secure high-efficiency electronic voting scheme based on homomorphic signcryption[J]. Future Generation Computer Systems, 2020, 111: 754-762.
  • [6] Yang X, Yi X, Nepal S, et al. A secure verifiable ranked choice online voting system based on homomorphic encryption[J]. IEEE Access, 2018, 6: 20506-20519.