Abstract
Mixnets are one of the main approaches to deploy secret and verifiable electronic elections. General-purpose verifiable mixnets however suffer from the drawback that the amount of data to be verified by observers increases linearly with the number of involved mix nodes, the number of decryptors, and the number of voters. Chase et al. proposed a verifiable mixnet at Eurocrypt 2012 based on so-called malleable proofs - proofs that do not increase with the number of mix nodes. In work published at PKC 2013, the same authors adapted malleable proofs to verifiable distributed decryption, resulting in a cryptographic voting scheme. As a result, the amount of data to be verified only increases linearly with the number of voters. However, their scheme leaves several questions open which we address in this paper: As a first contribution, we adapt a multi-party computation protocol to build a distributed key generation protocol for the encryption scheme underlying their voting scheme. As a second contribution, we decompress their abstract scheme description, identify elementary operations, and count the number of such operations required for mixing and verification. Based on timings for elementary operations, we extrapolate the running times of the mixing and verification processes, allowing us to assess the feasibility of their scheme. For the German case, we conclude that the replacement of postal voting by cryptographic voting based on malleable proofs is feasible on an electoral district level.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chaum, D.L.: Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM 24(2), 84–90 (1981)
Wikström, D.: A commitment-consistent proof of a shuffle. In: Boyd, C., González Nieto, J. (eds.) ACISP 2009. LNCS, vol. 5594, pp. 407–421. Springer, Heidelberg (2009)
Terelius, B., Wikström, D.: Proofs of restricted shuffles. In: Bernstein, D.J., Lange, T. (eds.) AFRICACRYPT 2010. LNCS, vol. 6055, pp. 100–113. Springer, Heidelberg (2010)
Wikström, D.: A commitment-consistent proof of a shuffle. Cryptology ePrint Archive, Report 2011/168 (2011), http://eprint.iacr.org/
Lipmaa, H., Zhang, B.: A More Efficient Computationally Sound Non-Interactive Zero-Knowledge Shuffle Argument. IACR Cryptology ePrint Archive, 394 (2011)
Bayer, S., Groth, J.: Efficient Zero-Knowledge Argument for Correctness of a Shuffle. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 263–280. Springer, Heidelberg (2012)
Chase, M., Kohlweiss, M., Lysyanskaya, A., Meiklejohn, S.: Malleable Proof Systems and Applications. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 281–300. Springer, Heidelberg (2012)
Boneh, D., Boyen, X., Shacham, H.: Short Group Signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)
Groth, J., Sahai, A.: Efficient Non-interactive Proof Systems for Bilinear Groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008)
Chase, M., Kohlweiss, M., Lysyanskaya, A., Meiklejohn, S.: Verifiable Elections That Scale for Free. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 479–496. Springer, Heidelberg (2013)
Geisler, M., Smart, N.P.: Distributing the Key Distribution Centre in Sakai–Kasahara Based Systems. In: Parker, M.G. (ed.) Cryptography and Coding 2009. LNCS, vol. 5921, pp. 252–262. Springer, Heidelberg (2009)
CertiVox: MIRACL Crypto SDK, https://certivox.com/solutions/miracl-crypto-sdk/ (accessed March 22, 2013)
Fouque, P.A., Poupard, G., Stern, J.: Sharing Decryption in the Context of Voting or Lotteries. In: Frankel, Y. (ed.) FC 2000. LNCS, vol. 1962, pp. 90–104. Springer, Heidelberg (2001)
Shamir, A.: How to share a secret. Communications of the ACM 22, 612–613 (1979)
Cramer, R., Damgård, I., Ishai, Y.: Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 342–362. Springer, Heidelberg (2005)
Pedersen, T.: A Threshold Cryptosystem without a Trusted Party. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 522–526. Springer, Heidelberg (1991)
Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 295–310. Springer, Heidelberg (1999)
Cramer, R., Damgård, I., Nielsen, J.B.: Multiparty Computation, an Introduction, http://www.cs.au.dk/~jbn/smc.pdf (accessed March 22, 2013)
Bar-Ilan, J., Beaver, D.: Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In: Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, Edmonton, Alberta, Canada, August 14-16, pp. 201–209. ACM (1989)
Kate, A., Goldberg, I.: Asynchronous distributed private-key generators for identity-based cryptography. IACR Cryptology ePrint Archive, 355 (2009)
McEliece, R.J., Sarwate, D.V.: On sharing secrets and Reed-Solomon codes. Communications of the ACM 24, 583–584 (1981)
Cohen, H., Frey, G. (eds.): Handbook of elliptic and hyperelliptic curve cryptography. CRC Press (2005)
Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006)
European Network of Excellence in Cryptology II: Ecrypt II Yearly Report on Algorithms and Key Sizes, http://www.keylength.com/en/3 (accessed March 22, 2013)
Ghadafi, E., Smart, N.P., Warinschi, B.: Groth–Sahai Proofs Revisited. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 177–192. Springer, Heidelberg (2010)
Smart, N.P.: Personal communication
CertiVox: CertiVox Wiki, Benchmarks and Subs, https://wiki.certivox.com/display/EXT/Benchmarks+and+Subs (accessed March 22, 2013)
Beuchat, J.L., Diaz, J.E.G., Mitsunari, S., Okamoto, E., Rodriguez-Henriquez, F., Teruya, T.: High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves. Cryptology ePrint Archive, Report 2010/354 (2010)
Mitsunari, S.: High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves, http://homepage1.nifty.com/herumi/crypt/ate-pairing.html (accessed March 22, 2013)
Der Bundeswahlleiter: Pressemitteilung (February 16, 2009)
Citizens Registration Office, D.E.M.N.: Personal communication
Smart, N.P.: Personal communication
Damgard, I., Keller, M., Larraia, E., Pastro, V., Scholl, P., Smart, N.P.: Practical Covertly Secure MPC for Dishonest Majority — or: Breaking the SPDZ Limits. Cryptology ePrint Archive, Report 2012/642 (2012)
Blazy, O., Fuchsbauer, G., Izabachène, M., Jambert, A., Sibert, H., Vergnaud, D.: Batch Groth–Sahai. In: Zhou, J., Yung, M. (eds.) ACNS 2010. LNCS, vol. 6123, pp. 218–235. Springer, Heidelberg (2010)
Knuth, D.: The Art of Computer Programming, vol. 4A. Addison-Wesley Professional (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bernhard, D., Neumann, S., Volkamer, M. (2013). Towards a Practical Cryptographic Voting Scheme Based on Malleable Proofs. In: Heather, J., Schneider, S., Teague, V. (eds) E-Voting and Identify. Vote-ID 2013. Lecture Notes in Computer Science, vol 7985. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39185-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-39185-9_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39184-2
Online ISBN: 978-3-642-39185-9
eBook Packages: Computer ScienceComputer Science (R0)