Abstract
This paper introduces weaknesses of two robust Mix-nets proposed in [10] and [7]. First, we show that [10] can lose anonymity in the presence of a malicious user even though all servers are honest. Second, we show that [7] can lose anonymity through the collaboration of a malicious user and the first server. The user can identify the plaintext sent from the targeted user by invoking two mix sessions at the risk of the colluding server receiving an accusation. We also point out that in a certain case, anonymity is violated solely by the user without colluding to any server. Practical repairs are provided for both schemes. Since such flaws are due to their weak security definitions, we present a stronger security definition by regarding a Mix-net as a batch decryption algorithm of a CCA secure public-key encryption scheme.
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.
References
M. Abe. Efficient Components for Cryptographic Applications in the Discrete-Log Setting. PhD thesis, University of Tokyo, 2002.
M. Abe and F. Hoshino. Remarks on mix-network based on permutation network. In K. Kim, editor, PKC 2001, volume 1992 of Lecture Notes in Computer Science, pages 317–324. Springer-Verlag, 2001.
R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143–202, Winter 2000.
D. L. Chaum. Untraceable electronic mail, return address, and digital pseudonyms. Communications of the ACM, 24:84–88, 1981.
Y. Desmedt and K. Kurosawa. How to break a practical MIX and design a new one. In Bart Preneel, editor, Advances in Cryptology — EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 557–572. Springer-Verlag, 2000.
J. Furukawa and K. Sako. An efficient scheme for proving a shuffle. In J. Killian, editor, Advances in Cryptology — Crypto 2001, volume 2139 of Lecture Notes in Computer Science, pages 368–387. Springer-Verlag, 2001.
P. Golle, S. Zhong, D. Boneh, M. Jakobsson, and A. Juels. Optimistic mixing for exit-polls. In Y. Zheng, editor, Advances in Cryptology — Asiacrypt 2002, volume 2501 of Lecture Notes in Computer Science, pages 451–465. Springer-Verlag, 2002.
H. Handschuh, Y. Tsiounis, and M. Yung. Decision oracles are equivalent to matching oracles. In H. Imai and Y. Zheng, editors, Second International Workshop on Practice and Theory in Public Key Cryptography, volume 1560 of Lecture Notes in Computer Science, pages 276–289. Springer-Verlag, 1999.
M. Jakobsson. A practical mix. In K. Nyberg, editor, Advances in Cryptology — EUROCRYPT’ 98, volume 1403 of Lecture Notes in Computer Science, pages 448–461. Springer-Verlag, 1998.
A. Juels and M. Jakobsson. An optimally robust hybrid mix network. In Proceedings of the 20th annual ACM Symposium on Principles of Distributed Computation, 2001.
A. Neff. A verifiable secret shuffle and its application to e-voting. In ACM CCS’01, pages 116–125. ACM, 2001.
M. Ohkubo and M. Abe. A length-invariant hybrid mix. In T. Okamoto, editor, Advances in Cryptology — ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science, pages 178–191. Springer-Verlag, 2000.
B. Pfitzmann. Breaking an efficient anonymous channel. In Alfredo De Santis, editor, Advances in Cryptology — EUROCRYPT’ 94, volume 950 of Lecture Notes in Computer Science, pages 339–348. Springer-Verlag, 1995.
K. Sako and J. Killian. Receipt-free mix-type voting scheme — a practical solution to the implementation of a voting booth —. In L. C. Guillou and J.-J. Quisquater, editors, Advances in Cryptology — EUROCRYPT’ 95, volume 921 of Lecture Notes in Computer Science, pages 393–403. Springer-Verlag, 1995.
C. P. Schnorr and M. Jakobsson. Security of signed Elgamal encryption. In T. Okamoto, editor, Advances in Cryptology — ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science, pages 73–89. Springer-Verlag, 2000.
D. Wikström. Four practical attacks for “optimistic mixing for exit-polls”. Technical Report SICS-T-2003/04-SE, Swedish Institute of Computer Science (SICS), February 2003. (Preliminary SICS-T-2002/24-SE, Dec. 2002).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abe, M., Imai, H. (2003). Flaws in Some Robust Optimistic Mix-Nets. In: Safavi-Naini, R., Seberry, J. (eds) Information Security and Privacy. ACISP 2003. Lecture Notes in Computer Science, vol 2727. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45067-X_4
Download citation
DOI: https://doi.org/10.1007/3-540-45067-X_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40515-3
Online ISBN: 978-3-540-45067-2
eBook Packages: Springer Book Archive