HAL编号：可信赖的分布式聚合保密数据的在线投票

0HAL编号：tel-017687870https://theses.hal.science/tel-017687870提交日期：2018年4月17日0HAL是一个多学科开放获取的存储库，用于存储和传播科学研究文档，无论其是否发表。这些文档可以来自法国或国外的教育和研究机构，或来自公共或私人研究中心。0HAL是一个多学科开放获取的存储库，用于存储和传播研究级科学文献，无论其是否发表，这些文献来自法国或国外的教育和研究机构，公共或私人研究中心。0迈向可信赖的在线投票：分布式聚合保密数据0Robert Riemann0引用此版本：0Robert Riemann. 迈向可信赖的在线投票：分布式聚合保密数据. 密码学与安全[cs.CR]. 里昂大学, 2017. 英文.�NNT: 2017LYSEN099�. �tel-01768787�0国家论文编号：2017LYSEN0990里昂大学博士学位论文0操作者：0里昂高等师范学校0博士学院编号5120里昂计算机科学和数学博士学院0学科：计算机科学0于2017年12月18日公开答辩：0Robert RIEMANN0迈向可信赖的在线投票：0分布式聚合保密0数据0在线投票的信任：0分布式聚合保密数据0评审委员会成员：0评审人：Pascal Lafourcade博士，讲师，克莱蒙费朗大学0评审人：Benjamin Nguyen博士，教授，INSA Centre Val de Loire0评审人：Antoinette Baujard博士，教授，让∙莫内大学0评审人：Stéphane Frénot博士，教授，INSA Lyon0导师：Stéphane Grumbach博士，Inria研究主任0评审人：Jörg Pohle博士，研究员，洪堡互联网与社会研究所（柏林）0[2018年4月11日10:54 - 版本e90d1ff]0[2018年4月11日10:54 - 版本e90d1ff]0Robert Riemann0迈向可信赖的在线投票：分布式聚合保密数据0[2018年4月11日10:54 - 版本e90d1ff]0[2018年4月11日10:54 - 版本e90d1ff]0里昂大学博士学位论文0操作者：0里昂高等师范学校0论文0迈向可信赖的在线投票：分布式聚合保密数据0作者：RobertRiemann0导师：StéphaneGrumbach博士0提交给InfoMaths博士学院（ED512）的博士学位论文，部分满足哲学博士学位要求0学科：计算机科学0公开答辩日期：2017年12月18日，里昂0[2018年4月11日10:54 - 版本e90d1ff]0RobertRiemann：迈向可信赖的在线投票：分布式聚合保密数据 © 2017年9月0[2018年4月11日10:54 - 版本e90d1ff][ 11th April 2018 at 10:54 – version e90d1ff ]0摘要0保证过程的稳健性和结果的正确性的同时，聚合需要保密的值对于越来越多的应用程序来说是必要的。各种调查，如医学调查、民意调查、公投、选举，以及物联网的新服务，如家庭自动化，都需要聚合保密数据。一般来说，保密性是基于可信第三方或密码学承诺来确保的，而这些能力在没有专业知识的情况下无法评估。本论文的目标是减少对权威和技术的信任需求，并探索大规模数据聚合的方法，既确保高度保密性，又不依赖于可信第三方或仅仅依赖于密码学。受到BitTorrent和Bitcoin的启发，考虑了P2P协议。本论文的第一个贡献是扩展分布式聚合协议BitBallot，目的是覆盖包含具有故障停止或拜占庭行为的对等节点的P2P网络中的聚合。引入的改变最终允许在存在对抗性少数派的情况下保持准确的结果。遇到的可扩展性限制导致第二个贡献，目标是支持大规模聚合。受到BitBallot和BitTorrent的启发，提出了一种名为ADVOKAT的新型分布式协议。在这两个协议中，对等节点被分配到树形覆盖网络的叶节点，该网络确定了中间聚合的计算并限制了数据的交换。在网络中的数据和计算的分区限制了数据泄露的可能性，并减少了对权威的信任需求。这些协议提供了一个中间件层，其灵活性通过投票和抽奖应用程序得到证明。R E S U M EL’agrégation des valeurs qui doivent être gardées confidentielles touten garantissant la robustesse du processus et l’exactitude du résultatest nécessaire pour un nombre croissant d’applications. Divers typesd’enquêtes, telles que les examens médicaux, les référendums, les élec-tions, ainsi que les nouveaux services de Internet of Things, tels que ladomotique, nécessitent l’agrégation de données confidentielles. En gé-néral, la confidentialité est assurée sur la base de tiers de confiance oudes promesses de cryptographie, dont les capacités ne peuvent êtreévaluées sans expertise.L’ambition de cette thèse est de réduire le besoin de confiance dansles autorités, de même que la technologie, et d’explorer les méthodesd’agrégations de données à grande échelle, qui garantissent un degréélevé de confidentialité et ne dépendent ni de tiers de confiance ni decryptographie. Inspiré par BitTorrent et Bitcoin, les protocoles P2P sontconsidérés.La première contribution de cette thèse est l’extension du protocoled’agrégation distribuée BitBallot dans le but de couvrir les agrégationsdans les réseaux P2P comprenant des pairs adversaires avec un com-portement défaillant ou byzantin. Les changements introduits permet-tent éventuellement de maintenir un résultat précis en présence d’uneminorité adversaire.Les limites de scalabilité rencontrées conduisent à la deuxième contri-bution dans le but de soutenir les agrégations à grande échelle. Ins-piré par BitBallot et BitTorrent, un nouveau protocole distribué appeléADVOKAT est proposé.Dans les deux protocoles, les pairs sont affectés aux noeuds feuillesd’un réseau de superposition d’une structure arborescente qui déter-mine le calcul des agrégats intermédiaires et restreint l’échange de don-nées. La partition des données et du calcul entre un réseau de pairséquipotent limite le risque de violation de données et réduit le besoinde confiance dans les autorités. Les protocoles fournissent une couchemiddleware dont la flexibilité est démontrée par les applications devote et de loterie.[ 11th April 2018 at 10:54 – version e90d1ff ]P U B L I C AT I O N SThe following publications contributed to the work presented in thisdissertation:Riemann, Robert and Stéphane Grumbach (2017a). ‘Distributed Pro-tocols at the Rescue for Trustworthy Online Voting’. In: Proc. ofthe 3rd International Conference on Information Systems Security andPrivacy (ICISSP). Porto, pp. 499–505. isbn: 978-989-758-209-7. doi:10.5220/0006228504990505. url: https://hal.inria.fr/hal-01501424.—(2017b). ‘Secure and trustable distributed aggregation based onKademlia’. In: IFIP Advances in Information and Communication Tech-nology. Ed. by F. Martinelli and S. De Capitani di Vimercati. Vol. 502.Rome: Springer. Chap. 12, pp. 171–185. isbn: 978-3-319-58468-3. doi:10.1007/978-3-319-58469-0_12. url: https://hal.inria.fr/hal-01529326.—(2017c). ‘Distributed Random Process for a large-scale Peer-to-PeerLottery’. In: Proc. of 17th IFIP Distributed Applications and Interoper-able Systems. DAIS’17. Neuchâtel: Springer, pp. 34–48. isbn: 978-3-319-59664-8. doi: 10.1007/978- 3- 319- 59665- 5_3. url: https://hal.inria.fr/hal-01583824.[ 11th April 2018 at 10:54 – version e90d1ff ][ 11th April 2018 at 10:54 – version e90d1ff ]AC K N OW L E D G E M E N T SIn spring 2013, I read for the first time the research proposal for a dis-tributed voting protocol. At that time, I was living in the only youthhostel of the French Caribbean island Guadeloupe and from there, Ihad my first video conference with my future supervisor Stéphane.However, only on detours and with the great support of Stéphane, Istarted in 2014 finally my journey with the ambitious project to exploremeans for more trustworthy online voting.During the three years of my doctoral studies, I enjoyed much free-dom and received the continuous support of the team–also in the dif-ficult second year when submissions were rejected and pursued ideasappeared to be dead ends. Many thanks for this to the DICE team, mostimportantly Stéphane, Stéphane, Damien, Aurélien and Étienne.Next to my scientific accomplishments, I made progress in few otherdomains, too. I became a fluent French speaker which has been a per-sonal goal for long. Stéphane made me aware of my many unfoundedpersonal convictions about society and the impact of new technology.I believe to be much more critic now. His lessons on scientific writingwere often very depressing for me, but eventually I think I managed toadopt high standards and do not want to miss his writing school.I thank the INSA Lyon IT department for the opportunity to teachand especially Vincent and Sylvie for their support. For the discussionvisit at the LIMOS lab in Clermont-Ferrand, I want to thank Pascal andMatthieu. For the research stay in summer 2017, I thank the HumboldtInstitute for Internet and Society in Berlin and in particular Jörg.I look back with gratefulness to the time I spent with my office mate,motivator and dancing teacher Aurélien. Thanks to him, I discovereda new world and made many new friends. I also want to thank my col-league Rodrigo. We spent during the last year many evenings, nightsand week-ends together in the office. Without him and his motivation,I would not have been able to keep up with the high workload and Ifeel bad, because I could not support him during the last months ofhis thesis. The IXXI lab at the ENS Lyon was my second home dur-ing my time in Lyon and I want to thank all colleagues that welcomedme with open arms, joined the discussions, also the diverting once onFrench culture, food, politics, society etc. Sam helped me so much inanswering my nitpicker grammar questions. Thank you all!I thank my defence committee and especially my thesis assessorsPascal and Benjamin for their commitment and feedback.Lastly, I also want to thank my family and friends, who supportedme throughout my stay abroad and were very forgiving in times whenI could not be there. I promise to improve.[ 11th April 2018 at 10:54 – version e90d1ff ][ 11th April 2018 at 10:54 – version e90d1ff ]CO N T E N T S1introduction11.1Problem Statement31.2Thesis Statement41.3Contributions42background52.1Challenges62.1.1Adversary Model72.1.2Protocol Properties72.1.3Public Perception92.2Historical Context92.2.1Voting in Ancient Greece112.2.2Towards Secret Paper-based Voting122.2.3Mechanisation142.2.4Electronic Voting162.3Voting Systems172.3.1Plurality Systems182.3.2Proportional Systems202.3.3Mixed Systems202.3.4Lottery Voting in Medieval Venice212.4Paper-based Voting212.4.1Preparation Phase212.4.2Casting Phase222.4.3Aggregation and Evaluation Phase222.4.4Verification Phase222.4.5Obsolescence of Paper-based Voting232.5Online Voting242.5.1Public Debate252.5.2Selected Trials252.6Scope of Applications282.6.1Lottery282.6.2Auctions292.6.3Aggregation of Sensitive Data293state of the art313.1Secure Online Aggregation323.1.1Trusted Authorities333.1.2Anonymous Voting333.1.3Random Perturbation353.1.4Homomorphic Encryption353.1.5Secret Sharing373.1.6Secure Multi-Party Computation393.2Distributed Protocols403.2.1Distributed Hash Tables40[ 11th April 2018 at 10:54 – version e90d1ff ]3.2.2File Sharing433.2.3Cryptocurrencies and Blockchains443.3Taxonomy483.4Summary514bitballot554.1Design Goals554.2Principle Concepts564.2.1Pull Principle564.2.2Aggregation over a Tree574.2.3Aggregation Algebra594.3Protocol Description604.3.1Preparation Phase614.3.2Aggregation Phase624.3.3Evaluation Phase634.4Original Implementation634.5Protocol Properties and Identified Issues644.5.1Security-Related Properties654.5.2System-Wide Properties674.5.3Summary694.6Extensions704.6.1Absent Peers704.6.2Dishonest Peers724.7Implementation of Extensions784.8Summary815advokat835.1Design Goals835.2Principle Concepts845.2.1Peer Discovery provided by Kademlia845.2.2Aggregation over a Binary Tree855.2.3Distributed Tree Configuration865.2.4Consensus on Intermediate Aggregates875.2.5Blocking Dishonest Peers895.3Protocol Description925.3.1Preparation Phase935.3.2Aggregation Phase955.3.3Evaluation Phase1025.4Protocol Properties and Identified Issues10305.4.1 与安全相关的属性05.4.2 系统范围的属性05.4.3 总结05.5 实施和模拟05.5.1 实施细节05.5.2 评估05.6 总结06 分布式在线投票06.1 引言0[2018年4月11日10:54 - 版本e90d1ff]06.2 协议描述06.2.1 设置阶段06.2.2 准备阶段06.2.3 注册的验证06.3 实施06.4 总结07 分布式在线抽奖07.1 引言07.2 相关工作07.3 集中式在线抽奖协议07.4 分布式在线抽奖协议07.4.1 设置阶段07.4.2 准备阶段07.4.3 聚合阶段07.4.4 评估阶段07.4.5 验证阶段07.5 协议属性07.5.1 最可能的情况07.5.2 最坏情况07.6 实施07.7 总结08 结论0BitBallot拉取原则的分析0附录A.1 可扩展性0附录A.2 机密性0参考文献0[2018年4月11日10:54 - 版本e90d1ff]0图表目录0图2.1 在Wine Cup with the Suicide ofAjax的场景中使用psephoi（鹅卵石）进行投票0图2.2 县选举（细节）0图2.3 Automatic Voting Corporation的杠杆投票机0图3.1 Kademlia �-buckets的示例0图4.1 根据BitBallot的拉取原则，输入流向对等方��的示例流程0图4.2根据BitBallot的拉取原则，信息流向具有叶节点��的对等方��的示例流程0图4.3 移动应用程序BitBallot的屏幕截图0图4.4 BitBallot的可扩展性和机密性0图5.1 ADVOKAT中签名的合格性0图5.2 ADVOKAT中的共识0图5.3 ADVOKAT中检测不诚实的对等方0图5.4 ADVOKAT中聚合物的拉取和确认0图5.5 ADVOKAT中偏差的证明0图5.6 ADVOKAT中泄露和接收的信息0图5.7 ADVOKAT中接收和发送的请求0图6.1 ADVOKAT-Vote序列图0图6.2 前端应用程序ADVOKAT-Vote的屏幕截图0图7.1 ADVOKAT-Lottery应用程序的屏幕截图0表格目录0表3.1 选定在线投票协议的分布质量0表A.1在具有136个元素的响应集中，具有k个不同获取的聚合物的概率��，�0[2018年4月11日10:54 - 版本e90d1ff]CAScentral authentication service.DDoS attackdistributed denial of service attack.DHTdistributed hash table.FPTP votingfirst past the post voting.KIDKademlia leaf node ID.PBBpublic bulletin board.PKIpublic key infrastructure.RPCremote procedure call.SMCsecure multi-party computation.[ 11th April 2018 at 10:54 – version e90d1ff ]0缩写词[ 11th April 2018 at 10:54 – version e90d1ff ]1I N T RO D U C T I O NIn today’s complex society, we often trust systems more than people.— Bruce Schneier (2012)A foundation pillar of our ever evolving society of increasing size andcomplexity is the cooperation among individuals. Cooperation relieson trust. In small communities, an important source of trust is the per-‘Trust is a bet aboutthe future contingentactions of others.’—Piotr Sztompkasonal relationships among its members. However, with growing size, itbecomes eventually infeasible to maintain personal relationships amongall members. Cooperation in large communities may instead rely on in-stitutional trust, i. e. trust in authorities. For instance, people may havetrust in fair judgements of an independent law court without having aprior personal relationship to the judges. Similarly, people may havetrust in the banking system, the police, social welfare system, and soon. Schneier (2012) argues that people feel easier nowadays to havetrust in institutions than in people. Trusting authorities is reasonableif they are appointed by many people that enforce compliance usingchecks and balances. In this case, the risk of defects due to a dishonestminority is effectively lowered.Where trust is insufficient or cannot be established, cooperation maybe based on security, i. e. physical constraints on behaviour of peopleregardless their trustworthiness. In situations where the security mech-anism is difficult to understand and to verify, trust in the capacityof the mechanism is required that shall be denoted technological trust.While online banking may in fact be secure, expert knowledge is neces-sary to verify the capacity of the algorithms that enforce security. Withno expert knowledge, people rely again on trust in the technology orthe assertions of trusted experts. Generally, more technology allows forlarger cooperation and increase both the dependence on institutionaland technological trust.Cooperation can be characterised by its size measured in the numberof involved members. Forms of large cooperation of global extensioninclude international trade, intergovernmental organisations, interna-tional NGOs, as well as the Internet. The Internet again is the basis forsocial networks and, more generally, platforms, which govern coopera-tion and intermediation of unprecedented size. For instance, the socialnetwork Facebook (2017) reports of 2 billion monthly active members,which is approximately a quarter of the world population and presum-ably the majority of all internet users.Large-scale cooperation entails more technological and often moreinstitutional trust and thus bears an important risk. Dishonest author-[ 11th April 2018 at 10:54 – version e90d1ff ]