瑞士邮政电子投票系统应该如何运作，又有什么问题呢？

#1 楼

在《瑞士邮政》的电子投票协议中，选民提交选票后，他们会被单独打乱并混在一起，以致无法追溯到选民中谁在选票之前就为谁投票（通常称为选票保密，隐私或匿名）。 ..

但是，由于选票是电子系统中的小部分，而不是物理制品，因此在实施洗牌机的计算机中，在魔术振动的硅晶体内部制造洗牌后的选票很容易。因此，洗牌者还必须打印出一张收据，世界上任何人都可以用来证明这只是一次洗牌，而不是任何其他形式的更改（选举的普遍可验证性的一部分），同时还要保持秘密，说明谁为谁投票。 br />
和任何具有投票保密性的电子投票协议一样，瑞士邮政协议中的通用验证方法涉及很多复杂的数学运算。事实证明，数学的设计方法使投票洗牌者能够伪造一张伪造的“洗牌”收据，从而改变选举结果。

它如何工作？


让$ m_1，m_2，\ dots，m_n $代表选举中填写的选票。我们想保留选票的秘密，但要计算选票的票数，并让公众核实选票的票数。


民意调查人员可以查看谁提交了每个选票$ m_i $，因此我们首先将选票加密为$ c_i = E_k（m_i，\ rho_i）$以将其隐藏于将其放入选票中的民意测验人员中，其中$ E_k（m，\ rho）$是具有随机$ \ rho $。随机化意味着民意调查人员不能只为每个可能的投票$ b $检查$ c_i = E_k（b）$是否恢复$ m_i $是什么。

投票计数器，谁知道秘密密钥，然后将一堆加密的选票解密，解密并计算结果。


由于民意测验工作人员可以按顺序投票表决，因此我们寻求投票洗牌机的帮助，将投票打乱为$ c _ {\ pi（1）}，c _ {\ pi（2）}，\ dots， c _ {\ pi（n）} $进行秘密排列$ \ pi $。*


因为投票计数器可以使$ c _ {\ pi（i）} $眼球辨别是否它与$ c_j $相同，从而恢复$ \ pi $的含义，我们还要求投票洗牌机在不更改其隐藏的投票的情况下对每个投票进行加扰。消息和随机化，即$$ E_k（m_1 m_2，\ rho_1 + \ rho_2）= E_k（m_1，\ rho_1）\ cdot E_k（m_2，\ rho_2），$$然后我们可以用$$ c来对票进行打乱_i = c _ {\ pi（i）} \ cdot E_k（1，\ rho'_i）= E_k（m _ {\ pi（i）}，\ rho _ {\ pi（i）} + \ rho'_i）$$进行秘密随机分配$ \ rho'_i $。*，然后将$ c'_1，c'_2，\ dots，c'_n $传递给投票计数器。




公众成员只有自己的收据$ c_i $，没有私钥的收据彼此之间以及与$ c都没有区别'_i $。要确信投票计数器或洗牌机不会通过用某些恶意的$ \ hat m_i $代替$ m_i $来欺诈性地改变选举结果，那么该系统必须对公众可验证。

同态随机公共密钥加密方案的典型示例是Elgamal加密$ E_k（m，\ rho）：=（g ^ \ rho，k ^ \ rho \ cdot m）$其中$ g，k，m \ in G $是一组$ G $的元素，其中离散的日志比较困难，而$ k $的秘密密钥是指数$ x $，因此$ k = g ^ x $。这里密文的乘积$（a，b）\ cdot（c，d）$是元素级的，$（a \ cdot c，b \ cdot d）$。

多年来，有许多系统具有不同程度的效率，以证明洗牌机发送给计票器的理货实际上是$ c _ {\ pi（i）} \ cdot E_k（ 1，\ rho'_i）$。‡其中之一是Bayer–Groth（全文）。在数十年的工作基础上，有很多加密技术可以提供有效的非交互式零知识证明—任何公众都可以离线使用以确认$ c'_i $实际上是$ c _ {\ pi（i）} \ cdot E_k（1，\ rho'_i）$，而无需了解$ \ pi $或$ \ rho'_i $是什么。

关键的部分是使用Pedersen承诺通过共享承诺$$ \ operatorname {commit} _r（a_1，a_2，\ dots，a_n）：= g_1 ^ { a_1} g_2 ^ {a_2} \ cdots g_n ^ {a_n} h ^ r，$$其中G $中的组元素$ g_1，g_2，\ dots，g_n，h \ in是独立地随机选择的。

如果没有$ r $，则承诺本身不会提供有关$（a_1，a_2，\ dots，a_n）$的信息，因为如果$ r $是统一的，则所有承诺都是等价的，也就是说，Pedersen承诺在信息论上是隐藏的。但是承诺和随机化$ r $使任何人都可以验证任何假定的$（a'_1，a'_2，\ dots，a'_n）$的等式，从而可以确信它们是$（a_1，a_2，\ dots ，a_n）$首先用于创建承诺：如果您可以找到不同的序列$（a'_1，a'_2，\ dots，a'_n）\ ne（a_1，a_2，\ dots，a_n） $和随机数$ r'$，其中$$ \ operatorname {commit} _r（a_1，a_2，\ dots，a_n）= \ operatorname {commit} _ {r'}（a'_1，a'_2，\ dots， a'_n），$$，则可以计算彼此相对的$ h $和$ g_i $的离散日志-一个精妙的总结是Pedersen承诺在离散日志假设下具有计算约束力。 （证明：如果$ g_1 ^ {a_1} h ^ r = g_1 ^ {a'_1} h ^ {r'} $，则$ \ log_ {g_1} h = \ frac {a'_1-a_1} {r- r'} $。）

拜耳-格罗斯洗牌者使用Pedersen承诺在一个收据上承诺一个$ \ pi $和一个随机值$ \ rho'_i $，公众可以用来验证提交给投票柜台的一组投票。如果投票改组者可以撒谎并声称使用排列$ \ pi $，而实际上他们使用的是重复某些投票而放弃其他投票的功能，那么他们可能会欺诈性地更改选举结果。 Lewis–Pereira–Teague的论文详细介绍了该方法的工作原理。



查看Peersen承诺依赖的一种方法是离散对数问题似乎很难，所以我们只需要随机地均匀一致地独立选择承诺基础$ g_1，\ dots，g_n，h $。

随机地均匀一致地选择组元素的明显方法是选择指数$ e_1 ，\ dots，e_n，f $分别独立地随机均匀地设置$ g_1：= g ^ {e_1}，\ dots，g_n：= g ^ {e_n}，h：= g ^ f $。这是Scytl / Swiss Post系统的工作方式。 ，这方面的知识将使投票洗牌者能够进行基本上任意的投票欺诈-就像Dual_EC_DRBG基本点一样。附录A.2.3，这可能会使后门指数的学习变得困难，并且可以进行验证；据称这是Scytl选择解决此问题的方法，尽管我不知道他们是否已发布进行验证所需的哈希原像。



这可能听起来像是一个微不足道的错误：哎呀，我们忘了零秘密。但这说明了一个更深层次的问题。

承诺基础$ g_1，\ dots，g_n，h $用作标准技术（无付费墙）中的常见参考字符串，用于将交互式零知识证明系统转换为非交互式零知识证明收据，例如投票

在交互式证明系统中，验证者可能会选择一个无法预测的挑战，如证明阿里巴巴和40名小偷的故事中的哪条隧道出了证明者必须正确回答。如果我们想制作一个非交互式的证明收据，然后将其发布在网站上，以供公众下载和验证？



在某些协议中，像签名方案（例如使用菲亚特-沙米尔启发式算法得出的Schnorr签名方案）一样，可以用随机预言代替挑战：证明者可以对成绩单进行评估的随机函数，以模仿验证者可能提交的不可预测的挑战，证明者无法控制。为了实例化这样的协议，我们选择了像SHAKE128这样的哈希函数，我们希望它没有证明者可以用来伪造欺诈性证明的有用属性。据报道，这里详细描述的缺陷，同一位研究人员报告了在滥用菲亚特-沙米尔启发法方面的另一个使欺诈欺诈的缺陷—设计师忽略了将承诺值的整个笔录输入到哈希函数（“随机预言”）中，对于菲亚特-沙米尔启发法的安全性至关重要。尽管NSWEC的公众声称不受影响（存档），但该缺陷也出现在基于Scytl软件的新南威尔士州选举委员会的iVote系统中。类似地，在某些协议（如Bayer-Groth）中，我们可以使用公共参考字符串：随机选择的预先确定的位字符串，并预先由验证者和证明者知道。要实例化此类协议，我们需要一个系统来预先选择随机字符串，证明者可以利用证明者利用其属性的可能性很小，就像使用FIPS 186-4附录A.2.3所获得的那样。如果证明者可以影响公共参考字符串，则证明没有任何意义。

这是密码系统安全性合同的一部分。为了获得AES-GCM的任何安全性，您的责任是随机选择统一的密钥并将其保密，并且永远不要以同一随机数重复使用它。为了从Bayer-Groth投票洗牌机中获得任何担保，核实人和证明人必须事先同意证明人无权控制的公共参考字符串。在Scytl系统中，证明者选择了公共参考字符串。这不仅违反了安全合同，而且还显示出深刻的理解他们使用的非交互式零知识证明系统的基本前提。


公开证据不清楚关于作者是否知道这将作为后门，Lewis-Pereira-Teague的论文警告说，这可能是无能的产物，而不是恶意的-该缺陷的技术性质自2017年以来已为人所知（存档），不清楚是否了解后果。 NIST可能采用了Dual_EC_DRBG，这可能是不称职的-NIST早就意识到基点有些混乱，并且被NSA告知不要讨论。第一要务不是争辩软件供应商Scytl是恶意的还是不称职的，而是要由选举当局充分重视，以要求对设计进行真正的审查，而不是在部署之前受到NDA的假冒伪善赏金；回顾一下我们如何到达这里的过程，以确保这样的后门设计永远都不能接近在真实选举中部署，因为它们可以实现极其廉价的任意大规模，不可验证的投票欺诈。

（一个可以争论更大的问题是由于电子投票中无法检测到的集中欺诈；邮件投票中的分布式欺诈；还是由于选民的压制，重罪剥夺公民权以及关闭投票站而引起的；人们还可以争论其他IT问题，例如纸张的重要性。追踪和强制性的风险限制审计等。应该有这样的论点，但是这个问题不是他们的论坛-考虑自愿参加选举工作而不是与您的议会交谈！这个问题是专门针对Scytl和Swiss Post滥用密码术的技术性质（无论是疏忽还是恶意的）。洗牌机的所有动作，以确保它们不会与其他人串通以显示秘密选票。无所不知的大规模监视制度也是诚实的，绝不会梦想与任何人自己勾结，而不是在不自觉的情况下进行勾结。

•投票计数器还必须能够证明其返回的计数是馈入该计数的加密选票的纯文本之和，在此我们将不做介绍-具体的后门正在讨论中的是洗牌机。

#2 楼

问题在于该方案的设计欠佳，特别是通用验证的一部分。

正如Ceci n'est pas une所指出的那样：

为了确保匿名性对方案进行表决，该方案利用依赖于拜耳和格罗斯（Pedersen承诺的概括）的混洗证明的混合网，然后进一步依赖离散对数假设。日志假设可以称为陷门承诺方案，因为它们依赖于这样的事实，即没人能学习离散日志。完全可以，但是：具体问题是由于在此方案的设计中承诺参数是随机生成的事实而引起的。此随机参数是用于获取离散对数的实际机密。此外，不能保证此值可以安全地从内存中删除。这样最终会破坏承诺方案。

因此，对手可以利用此问题，例如通过削弱PRNG的随机性来破坏PRNG。他们说（第9页）是有意引入此问题的：


我们的分析表明，没有故意引入此问题的。它完全与缺乏全面了解
安全性假设和其他重要细节的，有良好意图的人天真的实现复杂的加密协议相一致。当然，如果有人确实想引入一种操纵的机会，那么最好的方法就是如果被发现，可以将其解释为一种意外。我们根本看不到任何证据
。