Abstract
We propose a new mix network that is optimized to produce a correct output very fast when all mix servers execute the mixing protocol correctly (the usual case). Our mix network only produces an output if no server cheats. However, in the rare case when one or several mix servers cheat, we convert the inputs to a format that allows “back-up” mixing. This back-up mixing can be implemented using any one of a wide array of already proposed (but slower) mix networks. When all goes well, our mix net is the fast est, both in real terms and asymptotically, of all those that offer standard guarantees of privacy and correctness. In practice, this benefit far outweighs the drawback of a comparatively complex procedure to recover from cheating. Our new mix is ideally suited to compute almost instantly the output of electronic elections, whence the name “exit-poll” mixing.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Universally verifiable mix-net with verification work independent of the number of mix-servers. In Proc. of Eurocrypt’ 98, pp. 437–447. Springer-Verlag, 1998. LNCS 1403.
M. Abe. Mix-networks on permutation networks. In Proc. of Asiacrypt’ 99, pp. 258–273, 1999. LNCS 1716.
M. Abe and F. Hoshino. Remarks on mix-networks based on permutation networks. In Proc. of PKC’01.
D. Boneh. The Decision Diffie-Hellman Problem. In ANTS-III, pp. 48–63, 1998. LNCS 1423.
D. Boneh and M. Franklin. Efficient generation of shared RSA keys. In Proc. of CRYPTO’97, pp. 425–439. LNCS 1294.
M. Bellare and P. Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. In Proc. of CCS’93, pp. 62–73.
D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. In Communications of the ACM, 24(2):84–88, 1981.
D. Chaum and T. Pedersen. Wallet databases with observers. In Proc. of Crypto’92, pp. 89–105. Springer-Verlag, 1993. LNCS 740.
Y. Desmedt and Y. Frankel. Threshold cryptosystems. In Proc. of Crypto’89, pp. 307–315. LNCS 435.
Y. Desmedt and K. Kurosawa. How to break a practical MIX and design a new one. In Proc. of Eurocrypt’2000, pp. 557–572. LNCS 1807.
P. Feldman. A practical scheme for non-interactive verifiable secret sharing. In Proc. of the 28th IEEE Symposium on the Foundations of Computer Science, IEEE Press, 1987, pp. 427–437.
J. Furukawa, H. Miyauchi, K. Mori, S. Obana, K. Sako. An implementation of a universally verifiable electronic voting scheme based on shuffling. In Pre-proceedings of Financial Crypto’02.
A. Fiat and A. Shamir. How to prove yourself: practical solutions to identification and signature problems. In Proc. of CRYPTO’86, 1987.
J. Furukawa and K. Sako. An efficient scheme for proving a shuffle. In Proc. of Crypto’ 01, pp. 368–387. Springer-Verlag, 2001. LNCS 2139.
E. Gabber, P. Gibbons, Y. Matias and A. Mayer. How to make personalized Web browsing simple, secure and anonymous. In Proc. of Financial Cryptography’ 97, pp. 17–31, 1997.
R. Gennaro, S. Jarecki and H. Krawczyk and T. Rabin, Secure Distributed Key Generation for Discrete-Log Based Cryptosystems, In Proc. of Eurocrypt’ 99, pp. 295–310, 1999. LNCS 1592.
R. Gennaro, M. Rabin and T. Rabin. Simplified VSS and fast-track multi-party computations with applications to threshold cryptography. In Proc. ACM PODC’98, pp. 101–111.
M. Hirt and K. Sako. Efficient receipt-free voting based on homomorphic encryption. In Proc. of Eurocrypt’00, pp. 539–556. Springer-Verlag, 2000. LNCS 1807.
M. Jakobsson. A practical mix. In Proc. of Eurocrypt’ 98, pp. 448–461. Springer-Verlag, 1998. LNCS 1403.
M. Jakobsson and D. M’Raïhi. Mix-based electronic payments. In Proc. of SAC’98, pp. 157–173. Springer-Verlag, 1998. LNCS 1556.
M. Jakobsson. Flash mixing. In Proc. of PODC’ 99, pp. 83–89. ACM, 1999.
M. Jakobsson and A. Juels. Millimix: mixing in small batches. DIMACS Technical Report 99-33.
M. Jakobsson and A. Juels. An optimally robust hybrid mix network. In Proc. of PODC’01, pp. 284–292. ACM Press. 2001.
M. Jakobsson, A. Juels and R. Rivest. Making mix nets robust for electronic voting by randomized partial checking. To be presented at USENIX’02.
A. Kiayias and M. Yung. Self-tallying elections and perfect ballot secrecy. In Proc. of PKC’02, pp. 141–158. LNCS 2274.
M. Mitomo and K. Kurosawa. Attack for flash mix. In Proc. of Asi-acrypt’00, pp. 192–204. LNCS 1976.
A. Neff. A verifiable secret shuffle and its application to E-Voting. In Proc. of ACM CCS’01, pp. 116–125. ACM Press, 2001.
NIST. Secure hash standard. Federal Information Processing Standards Publication 180-1. 1995.
W. Ogata, K. Kurosawa, K. Sako and K. Takatani. Fault tolerant anonymous channel. In Proc. of ICICS’ 97, pp. 440–444, 1997. LNCS 1334.
P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Proc. of Eurocrypt’99, pp. 223–238. LNCS 1592.
T. Pedersen. A Threshold cryptosystem without a trusted party. In Proc. of Eurocrypt’91, pp. 522–526, 1991.
C. Park, K. Itoh and K. Kurosawa. Efficient anonymous channel and all/nothing election Scheme. In Proc. of Eurocrypt’ 93, pp. 248–259. Springer-Verlag, 1993. LNCS 765.
B. Pfitzmann and A. Pfitzmann. How to break the direct RSA-implementation of mixes. In Proc. of Eurocrypt’ 89, pp. 373–381. Springer-Verlag, 1989. LNCS 434.
B. Pfizmann. Breaking an efficient anonymous channel. In Proc. of Eurocrypt’ 94, pp. 339–348.
R. Rivest. The MD5 message-digest algorithm. IETF Network Working Group, RFC 1321, 1992.
K. Sako and J. Kilian. Receipt-free mix-type voting scheme. In Proc. of Eurocrypt’ 95. Springer-Verlag, 1995. LNCS 921.
C. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4:161–174, 1991.
Y. Tsiounis and M. Yung. On the security of ElGamal based encryption. In Proc. of PKC’98.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Golle, P., Zhong, S., Boneh, D., Jakobsson, M., Juels, A. (2002). Optimistic Mixing for Exit-Polls. In: Zheng, Y. (eds) Advances in Cryptology — ASIACRYPT 2002. ASIACRYPT 2002. Lecture Notes in Computer Science, vol 2501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36178-2_28
Download citation
DOI: https://doi.org/10.1007/3-540-36178-2_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00171-3
Online ISBN: 978-3-540-36178-7
eBook Packages: Springer Book Archive