Abstract
This paper addresses the security and efficiency issues of the Mix-net based on permutation networks introduced in [1]. We first show that the original construction results in a Mix-net that yields biased permutation, so it gives some advantage to adversaries. A simple repair is provided. We then observe that one of the original schemes can be improved so that the servers and verifier enjoy more efficient computation and communication.
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. Mix-networks on permutation networks. In K. Lam, E. Okamoto, and C. Xing, editors, Advances in Cryptology-Asiacrypt’ 99, volume 1716 of Lecture Notes in Computer Science, pages 258–273. Springer-Verlag, 1999.
M. Abe. Universally verifiable mix-net with verification work independent of the number of mix-servers. IEICE Transaction of Fundamentals of electronic Communications and Computer Science, E83-A(7):1431–1440, July 2000. Presented at Eurocrypt’98.
D. L. Chaum. Untraceable electronic mail, return address, and digital pseudonyms. Communications of the ACM, 24:84–88, 1981.
D. L. Chaum and T. P. Pedersen. Wallet databases with observers. In E. F. Brickell, editor, Advances in Cryptology-CRYPTO’ 92, volume 740of Lecture Notes in Computer Science, pages 89–105. Springer-Verlag, 1993.
R. Cramer, I. Damg∢rd, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Y. G. Desmedt, editor, Advances in Cryptology-CRYPTO’ 94, volume 839 of Lecture Notes in Computer Science, pages 174–187. Springer-Verlag, 1994.
Y. Desmedt and K. Kurosawa. How to break a practical MIX and design a new one. In B. Preneel, editor, Advances in Cryptology-EUROCRYPT 2000, volume 1807of Lecture Notes in Computer Science, pages 557–572. Springer-Verlag, 2000.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Secure distributed key generation for discrete-log based cryptosystems. In J. Stern, editor, Advances in Cryptology-EUROCRYPT’ 99, volume 1592 of Lecture Notes in Computer Science, pages 295–310. 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.
M. Jakobsson. Flash mixing. In PODC99, pages 83–89, 1999.
A. Juels and M. Jakobsson. Millimix. Technical Report 99-33, DIMACS Technical Report, June 1999.
M. Michels and P. Horster. Some remarks on a receipt-free and universally verifiable mix-type voting scheme. In K. Kim and T. Matsumoto, editors, Advances in Cryptology-ASIACRYPT’ 96, volume 1163 of Lecture Notes in Computer Science, pages 125–132. Springer-Verlag, 1996.
M. Mitomo and K. Kurosawa. Attack for flash MIX. In Asiacrypt 2000 (to appear), 2000.
W. Ogata, K. Kurosawa, K. Sako, and K. Takatani. Fault tolerant anonymous channel. In ICICS98, volume 1334 of Lecture Notes in Computer Science, pages 440–444. Springer-Verlag, 1998.
M. Ohkubo and M. Abe. A length-invariant hybrid mix. In Asiacrypt2000 (to appear), 2000.
C. Park, K. Itoh, and K. Kurosawa. Efficient anonymous channel and all/nothing election scheme. In T. Helleseth, editor, Advances in Cryptology-EUROCRYPT’ 93, volume 765 of Lecture Notes in Computer Science, pages 248–259. Springer-Verlag, 1994.
B. Pfitzmann. Breaking an efficient anonymous channel. In A. D. Santis, editor, Advances in Cryptology-EUROCRYPT’ 94, volume 950 of Lecture Notes in Computer Science, pages 339–348. Springer-Verlag, 1995.
B. Pfitzmann and A. Pfitzmann. How to break the direct RSA implementation of MIXes. In J.-J. Quisquater and J. Vandewalle, editors, Advances in Cryptology-Eurocrypt’ 89, volume 434 of Lecture Notes in Computer Science, pages 373–381. Springer-Verlag, 1989.
K. Sako. An improved universally verifiable mix-type voting schemes. Unpublished Manuscript, 1995.
K. Sako and J. Kilian. 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.
A. Waksman. A permutation network. Journal of the Association for Computing Machinery, 15(1):159–163, January 1968.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abe, M., Hoshino, F. (2001). Remarks on Mix-Network Based on Permutation Networks. In: Kim, K. (eds) Public Key Cryptography. PKC 2001. Lecture Notes in Computer Science, vol 1992. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44586-2_23
Download citation
DOI: https://doi.org/10.1007/3-540-44586-2_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41658-6
Online ISBN: 978-3-540-44586-9
eBook Packages: Springer Book Archive