×

Review of cryptographic schemes applied to remote electronic voting systems: remaining challenges and the upcoming post-quantum paradigm. (English) Zbl 1391.94779

Summary: The implantation of Remote Electronic Voting (REV) systems to Electoral Processes is happening at a slower pace than anticipated. One of the relevant factors explaining that reality is the lack of studies about the Cryptographic Schemes and Primitives applied to the existing REV solutions. In this paper, the authors review the main cryptographic schemes applied to date, as well as the most relevant Post Quantum research in the field. The aim is twofold: contribute to clarify the strengths and weaknesses of each scheme as well as expose the remaining challenges, as a necessary step towards a broader introduction of REV solutions in binding elections.

MSC:

94A60 Cryptography

Software:

Akiss; Helios; HElib; BKZ; FHEW
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Springall D., Finkenauer T., Durumeric Z., Kitcat J., Hursti H., MacAlpine M., et al. Security Analysis of the Estonian Internet Voting System, Proc 21st ACM Conf Comput Commun Secur., 2014, 703-715. · doi:10.1145/2660267.2660315
[2] Foundation USV. The Future of Voting. In: The Future of Voting [Internet]. Available: , 2015
[3] The FREAK Attack. In: The FREAK Attack [Internet]. Available: , 2015
[4] Adrian D., Bhargavan K., Durumeric Z., Gaudry P., Green M., Halderman JA., et al. Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. Proceedings of the 22Nd ACM SIGSAC Conference on Computer and Communications Security, New York, NY, USA, 2015, 5-17 · doi:10.1145/2810103.2813707
[5] Wang X., Yu H., How to Break MD5 and Other Hash Functions. Adv Cryptol - EUROCRYPT, 2005, 19-35 · Zbl 1137.94359 · doi:10.1007/114266392
[6] Goldwasser S., Tauman Y., On the (In)security of the Fiat-Shamir Paradigm. Focs, 2003
[7] Achenbach D., Kempka C., Lowe B., Muller-Quade J., Improved Coercion-Resistant Electronic Elections through Deniable Re-Voting. USENIX J Elect Technol Syst., 2015, 26-45
[8] Wolchok S., Wustrow E., Isabel D., Halderman JA., Attacking the Washington, D.C. Internet Voting System. System, International Conference on Financial Cryptography and Data Security, 2012, 114-128
[9] M C. Ukraine election narrowly avoided “wanton destruction” from hackers. In: Christian Science Monitor [Internet]. Available: , 2014
[10] Halderman JA., Teague V. The New South Wales iVote System: Security Failures and Verification Flaws in a Live Online Election. In: Haenni R., Koenig RE., Wikström D., editors. E-Voting and Identity: 5th International Conference, VoteID 2015, Bern, Switzerland, September 2-4, 2015 35-53. · doi:10.1007/978-3-319-22270-73
[11] Nakashima E., Arizona: Russian hackers targeted Arizona election system. The Washington Post., 2016
[12] Background to Assessing Russian Activities and Intentions in Recent US Elections: The Analytic Process and Cyber Incident Attribution, 2017
[13] Bernhard M., Election Recount Hacking Voting Machines. The Guardian, 2016
[14] Neumann SR., Ph.D. Thesis Evaluation and Improvement of Internet Voting Schemes Based on Legally-Founded Security Requirements, Technische Universität Darmstadt, Germany, 2016
[15] Marcos del Blanco DY., Panizo Alonso L., and Hermida Alonso JA., The need for Harmonization in the online voting field: Towards an European Standard for edemocracy. The International Conference on Electronic Voting, E-Vote-ID 2016, October 18-21, Bregenz, Austria, 2016, 339-343
[16] Directorate General of Democracy and Political Affairs. Certification of e-voting systems. Guidelines for developing processes that confirm compliance with prescribed requirements and standards. Council of Europe, 2011
[17] Gentry C., Fully homomorphic encryption using ideal lattices., In: Proceedings of the forty-first annual ACM symposium on Theory of computing May 31 - June 02 2009, Bethesda, MD, USA, 2009, 169-178 · Zbl 1304.94059
[18] Chillotti I., Gama N., Georgieva M., Izabachene M. An Homomorphic LWE based E-Voting Scheme In: 7th International Workshop, PQCrypto 2016, February 24-26, 2016, Fukuoka, Japan, 2016, 245-265 · Zbl 1405.81024
[19] Panizo L., Ph.D. Thesis Desarrollo de una metodología para el análisis y la clasificación de los sistemas de voto electrónico, University of Leon, Leon Spain, 2014 (in Spanish)
[20] Ronquillo L., Securing e-voting systems, lecture. 12 May 2015
[21] Fiat A., Shamir A., How to prove yourself: Practical solutions to identification and signature schemes, In: Advances in Cryptology Crypto’86 Springer-Verlag, 1986, 186-194
[22] Adida B., Helios: Web-based Open-audit Voting, In: Proceedings of the 17th Conference on Security Symposium, July 28 - August 1 2008, San Jose, CA, USA, 2008, 335-348
[23] Bernhard D., Pereira O., and Warinschi B. How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios, In: Advances in Cryptology ASIACRYPT 2012:18th International Conference on the Theory and Application of Cryptology and Information Security, December 2-6, Beijing, China, 2012, 626-643 · Zbl 1292.94029
[24] Kusters R., Truderung T., Vogt A., Clash Attacks on the Verifiability of E-Voting Systems, In: Proceedings of the 2012 IEEE Symposium on Security and Privacy, May 20-23 2012, San Francisco, CA, USA, 2012, 395-409
[25] ElGamal T., Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, In: G R Blakley and D Chaum (Eds.) Advances in Cryptology: Proceedings of CRYPTO 84, Berlin, 1985 469-472 · Zbl 0571.94014
[26] Sanou E., MSc Thesis Post-Quantum Cryptography: Lattice-based, Universitat Politecnica de Catalunya, Barcelona Spain, 2016
[27] Benaloh JDC., Rivest R., Ryan PYA., Stark P., Teague V., and Vora P., End-to-end verifiability arXiv e-prints, 2014
[28] Juels A., Catalano D. and Jakobsson M. Coercion-resistant electronic elections, In: Lecture Notes in Computer Science vol. LNCS 6000, 2010 37-63 · Zbl 1284.68247
[29] Blanchet B., An Automatic Security Protocol Verifier based on Resolution Theorem Proving (invited tutorial) In: Nieuwenhuis R. (Ed.) 20th International Conference on Automated Deduction, July 22-27, Tallinn, Estonia, 2005, 3-51
[30] Chadha R., Cheval V., Ciobaca S., and Kremer S. Automated Verification of Equivalence Properties of Cryptographic Protocols, 2012
[31] Cheval V. APTE: An Algorithm for Proving Trace Equivalence In: Abraham E. and Havelund K. (Eds.) Tools and Algorithms for the Construction and Analysis of Systems: 20th International Conference, TACAS 2014, part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014, April 5-13, Grenoble, France, 2014 587-592
[32] Cortier V., Formal Verification of e-Voting: Solutions and Challenges, ACM SIGLOG News, vol. 2, 1, 2015, 25-34
[33] Panizo L., Gasco M., Marcos del Blanco DY., Hermida JA. and Alaiz H. E-voting system evaluation based on the Council of Europe recommendations: Helios Voting IEEE Transactions on emerging topics in computing. Special issue on e-government development and applications (SIEGDA) (expected 2018), under review.
[34] Hirt M., Sako K. Efficient Receipt-Free voting based on homomorphic encryption In: Preneel B., editor, EUROCRYPT’00, vol. 1807 LNCS Bruges, Belgium, 2000, 539-556 · Zbl 1082.94520
[35] Achenbach D., Kempka C., Lowe B., Muller-Quade J. Improved Coercion-Resistant Electronic Elections through Deniable Re-Voting In: JETS, The Usenix Journal of Election Tech. and Systems, 12-14 August, Washington, USA, 2015, 26-45
[36] Smith R. Internet Voting and Voting Interference. A report for the New South Wales Electoral Commission , 2013
[37] Heiberg S., Parsovs A., Willemson J. Log Analysis of Estonian Internet Voting 2013 - 2015. Smartmatic - Cybernetica Centre of Excellence for Internet Voting, Software Technology and Applications Competence Centre, Tartu University, 2015
[38] Nore H., Implementing E-Voting in Norwegian Elections New Voting Technology Consulting AS, 2015
[39] Chung D., Bishop M., Peisert S. Distributed Helios - Mitigating Denial of Service Attacks in Online Voting University of California Davis, 2016
[40] Chandra TD., Griesemer R., Redstone J., Paxos made live: An engineering perspective. In: 26th Annual ACM Symposium on Principles of Distributed Computing, August 12-15, Portland, OR, USA, 2007, 398-407
[41] Chaum D. Untraceable electronic mail, return addresses and digital pseudonyms. ACM, 24(2), 1981, 84-90
[42] Fujioka A., Okamoto T., Ohta K. A practical secret voting scheme for large scale elections. ASIACRYPT’92, Workshop on the Theory and Application of Cryptographic Techniques, LNCS 718, Gold Coast, Australia, 1992, 244-251 · Zbl 1096.68612
[43] Haber S., Benaloh J. and Halevi S. The Helios e-Voting Demo for the IACR, 2010,
[44] Scytl, R&D Department. Articles and Publications. , 2017
[45] Perriard B. Vote electronique: the long path towards the digitalization of political rights Swiss Federal Chancellery, 2015
[46] Scytl Report French Ministry of Foreign Affairs. French Expats vote online in 2012 legisla-tive elections Available at: , 2012
[47] Rivest R., Shamir A., Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21, 1978, 120-126 · Zbl 0368.94005
[48] Paillier P. Public-Key Cryptosystems based on Composite-Degree Residuosity Classes. In: J Stern (Ed.) EUROCRYPT’99 May 2-6, Prague, Czech Republic, 1999, 223-238 · Zbl 0933.94027
[49] Koenig RE., Locher P, Haenni R. A Security Flaw in the Verification Code Mechanism of the Norwegian Internet Voting System Bern University of Applied Sciences, 2013
[50] Springall D., Finkenauer T., Durumeric Z., Kitcat J., Hursti H., MacAlpine M, Halderman JA. Security Analysis of the Estonian Internet Voting System. In: ACM CCS November 3-7 Scottsdale, Arizona, USA, 2014, 703-715
[51] Shor P. Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science November 20-22 Santa Fe, New Mexico, USA, 1994, 124-134
[52] RSA Laboratories, EMC Corporation. ”What is a Blind Signature Scheme, 2016
[53] Witteman M., van Woudenberg J., Menarini F. Defeating RSA multiply-always and message blinding countermeasures Riscure BV. The Netherlands, 2007 · Zbl 1284.94126
[54] Ibrahim S., Kamat M, Salleh M., Aziz SRA. Secure E-voting with Blind Signature. In: NCTT 2003 Proceedings, 4th National Conference on Telecommunication Technology, January 14-15 Shah Alam, Malaysia, 2003, 193-197
[55] Rivest R., Adleman L., and Dertouzos M. On data banks and privacy homomorphisms. Foundations of Secure Computation, Academia Press, 1978, 169-180
[56] Gentry C., Halevi S., and Smart NP. Homomorphic Evaluation of the AES Circuit. In: Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, August 19-23, Santa Barbara, CA, USA, 2012, 850-867 · Zbl 1296.94117
[57] Regev O. On lattices, learning with errors, random linear codes, and cryptography. In: H N Gabow and R Fagin, (Eds.) Proceedings of the 37th Annual ACM Symposium on Theory of Computing, May 21-24, Maryland, USA,2005, 84-93 · Zbl 1192.94106
[58] Lyubashevsky V., Peikert C., and Regev O. On ideal lattices and learning with errors over rings. In: Proc. of EUROCRYPT, vol. 6110 of LNCS May 30 - June 3 Monaco and Nice, Monaco, France, 2010, 1-23 · Zbl 1279.94099
[59] Ducas L. and Micciancio D. FHEW: Bootstrapping homomorphic encryption in less than a second. In: Eurocrypt 2015, April 26-30 Sofia, Bulgaria, 2015, 617-640 · Zbl 1370.94509
[60] Chen Y. and Nguyen PQ. BKZ 2.0: Better lattice security estimates. In: Wang X. and Lee DH. (Eds.) Asiacrypt 2011, Seoul (Korea,2011) 1-20 · Zbl 1227.94037
[61] Gama N., Izabachene M., Nguyen PQ., and Xie X. Structural lattice reduction: Generalized worst-case to average-case reductions. In: EUROCRYPT 2016, 2016, 528-558 · Zbl 1371.94635
[62] Micciancio D. and Peikert C. Trapdoors for lattices: Simpler, tighter, faster, smaller. In: Pointcheval D. and Johansson T. (Eds.) Eurocrypt 2012, April 15-19, Cambridge, UK, 2012, 700-718 · Zbl 1297.94090
[63] Gjosteen K., Strand M. A roadmap to fully homomorphic elections: Stronger security, better verifiability. IACR Cryptology ePrint Archive, 2017, 404-418
[64] OSCE Office for Democratic Institutions and Human Rights. Norway, Parliamentary Elections 9 September 2013, Final Report, 2013
[65] Kim M., Lee HT., Ling S., and Wang H. On the efficiency of FHE-based private queries. IEEE Transactions on Dependable and Secure Computing, 2016
[66] Smart NP. and Vercauteren F. Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen PQ. and Pointcheval D. (Eds.) Public Key Cryptography - PKC 2010, vol. 6056 LNCS, 2010, 420-443 · Zbl 1281.94055
[67] Brakerski Z., Gentry C., and Vaikuntanathan V. Fully homomorphic encryption without bootstrapping. Electronic Colloquium on Computational Complexity (ECCC), 2011
[68] Halevi S. and Shoup V. Bootstrapping for HElib. In: Oswald E. and Fischlin M. (Eds.), Advances in Cryptology - EUROCRYPT 2015, vol 9056 of LNCS, 2015, 641-670
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.