Abstract
A MIX net takes a list of ciphertexts (c 1, ..., c N) and outputs a permuted list of the plaintexts (m 1, ..., m N) without revealing the relationship between (c 1,..., c N) and (m 1, ...,m N). This paper first shows that the Jakobsson’s MIX net of Eurocrypt’98, which was believed to be resilient and very efficient, is broken. We next propose an efficient t-resilient MIX net with O(t 2) servers in which the cost of each MIX server is O(N). Two new concepts are introduced, existential-honesty and limited-open-verification. They will be useful for distributed computation in general.
A part of this research was done while the author visited the Tokyo Institute of Technology, March 4–19, 1999. He was then at the University of Wisconsin — Milwaukee.
A part of his research was funded by NSF CCR-9508528.
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
M. Abe, “Universally verifiable mix-net with verification work independent of the number of mix-centers,” Eurocrypt’ 98, pp. 437–447.
M. Abe, “A mix-network on permutation networks,” ISEC Technical report 99-10 (in Japanese) (May, 1999)
M. Abe, “Mix-networks on permutation networks,” Asiacrypt’ 99, pp. 258–273.
M. Bellare, A. Desai, D. Poincheval, P. Rogaway, “Relations among notions of security for public key encryption schemes,” Crypto’ 98, pp. 26–45.
M. Bellare, P. Rogaway, “Optimal asymmetric encryption-How to encrypt with RSA,” Eurocrypt’ 94, pp. 92–111.
D. Chaum, “Untraceable electronic mail, return addresses, and digital pseudonyms,” Communications of the ACM, Vol. 24, 1981, pp. 84–88.
D. Chaum, H. Van Antwerpen, “Undeniable signatures,” Crypto’ 89, pp. 212–216.
Y. Desmedt, Y. Frankel, “Threshold cryptosystems,” Crypto’ 89, pp. 307–315.
D. Dolev, C. Dwork, M. Naor, “Non-malleable cryptography,” STOC’ 91, pp. 542–552.
T. ElGamal, “A public-key cryptosystem and a signature scheme based on discrete logarithms,” Crypto’ 84, pp. 10–18.
A. Fujioka, T. Okamoto, K. Ohta, “A practical secret voting scheme for large scale elections,” Auscrypt’ 92, pp. 244–251.
R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, “Robust and efficient sharing of RSA functions,” Crypto’ 96, pp. 157–172.
M. Jakobsson, “A practical MIX,” Eurocrypt’ 98, pp. 448–461.
M. Jakobsson, D. M’Raihi, “Mix-based electronic payments,” SAC’98, pp. 157–173.
M. Jakobsson, “Flash mixing,” PODC’99, pp. 83–89.
M. Jakobsson, A. Juels “Millimix: Mixing in small batches,” DIMACS Technical report 99-33 (June 1999)
W. H. Mills, “Covering design I: coverings by a small number of subsets,” Ars Combin. 8, (1979), pp. 199–315.
W. Ogata, K. Kurosawa, K. Sako, K. Takatani, “Fault tolerant anonymous channel,” ICICS’ 97, pp. 440–444.
C. Park, K. Itoh, K. Kurosawa, “All/nothing election scheme and anonymous channel,” Eurocrypt’ 93, pp. 248–259.
T. P. Pedersen, “A threshold cryptosystem without a trusted party,” Eurocrypt’ 91, pp. 522–526.
B. Pfitzmann, A. Pfitzmann. “How to break the direct RSA-implementation of MIXes,” Eurocrypt’ 89, pp. 373–381.
D. Pointcheval, J. Stern, “Security proofs for signature schemes,” Eurocrypt’ 96, pp. 387–398.
R. Rees, D. R. Stinson, R. Wei, G. H. J. van Rees, “An application of covering designs: Determining the maximum consistent set of shares in a threshold scheme,” Ars Combin. 531 (1999), pp. 225–237.
K. Sako, J. Kilian, “Receipt-free mix-type voting scheme,” Eurocrypt’ 95, pp. 393–403.
C. P. Schnorr, “Efficient signature generation for smart cards,” Crypto’ 89, pp. 239–252.
C. P. Schnorr, M. Jakobsson, “Security of discrete log cryptosystems in the random oracle + generic model,” http://www.bell-labs.com/user/markusj/
A. Shamir, “How to share a secret,” Communications of the ACM, Vol. 22, 1979, pp. 612–613
Y. Tsiounis, M. Yung, “On the security of ElGamal based encryption,” PKC’98, pp. 117–134.
Edited by C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Design, CRC Press (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Desmedt, Y., Kurosawa, K. (2000). How to Break a Practical MIX and Design a New One. In: Preneel, B. (eds) Advances in Cryptology — EUROCRYPT 2000. EUROCRYPT 2000. Lecture Notes in Computer Science, vol 1807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45539-6_39
Download citation
DOI: https://doi.org/10.1007/3-540-45539-6_39
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67517-4
Online ISBN: 978-3-540-45539-4
eBook Packages: Springer Book Archive