More Web Proxy on the site http://driver.im/

Article

An optimally robust hybrid mix network

Authors:

Markus Jakobsson,

Ari JuelsAuthors Info & Claims

PODC '01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing

Pages 284 - 292

https://doi.org/10.1145/383962.384046

Published: 01 August 2001 Publication History

Abstract

We present a mix network that achieves efficient integration of public-key and symmetric-key operations. This hybrid mix network is capable of natural processing of arbitrarily long input elements, and is fast in both practical and asymptotic senses. While the overhead in the size of input elements is linear in the number of mix servers, it is quite small in practice. In contrast to previous hybrid constructions, ours has optimal robustness, that is, robustness against any minority coalition of malicious servers.

References

[1]

M. Abe. Universally verifiable mix-net with verification work independent of the number of mix-servers. In K. Nyberg, editor, EUROCRYPT '98, pages 437- 447. Springer-Verlag, 1998. LNCS No. 1403.]]

[2]

M. Abe. A mix-network on permutation networks. In K.Y. Lain, C. Xing, and E. Okamoto, editors, ASI- ACRYPT '99, pages 258-273, 1999. LNCS no. 1716.]]

Digital Library

[3]

D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the A CM, 24(2):84-88, 1981.]]

Digital Library

[4]

D. Chaum and T.P. Pedersen. Wallet databases with observem. In E.F. Brickell, editor, CRYPTO '9, pages 89-105. Springer-Verlag, 1992. LNCS no. 740.]]

Digital Library

[5]

R. Cramer, I. Damgard, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In CRYPTO '9, pages 174-187. Springer-Verlag, 1994. LNCS No. 839.]]

Digital Library

[6]

A. de Santis, G. di Crescenzo, G. Pemiano, and M. Ytmg. On monotone formula closure of SZK. In FOCS '9, pages 454-465. IEEE Press, 1994.]]

[7]

Y. Desmedt and K. Kurosawa. How to break a practical mix and design a new one. In B. Preneel, editor, EU- ROURYPT '00, pages 557-572. Springer-Verlag, 2000. LNCS no. 1807.]]

[8]

A. Fiat and A. Shamir. How to prove yourselfi Practical solutions to identification and signature problems. In J. L. Massey, editor, EUROURYPT '86, pages 186-194. Springer-Verlag, 1986. LNCS no. 263.]]

Digital Library

[9]

E. Gabber, P. Gibbous, Y. Matias, and A. Mayer. How to make personalized Web browsing simple, secure, and anonymous. In R. Hirschfeld, editor, Financial Cryptography '97, pages 17-31, 1997.]]

Digital Library

[10]

R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold DSS signatures. In U. Maurer, editor, EUROCRYPT '96, pages 354-371. Springer- Verlag, 1996. LNCS no. 1070.]]

[11]

R. Gennaro, S. Jarecki, H. Krawczyk, and T. R- bin. The (in)security of distributed key generation in dlog-based cryptosystems. In J. Stern, editor, EU- ROCRYPT "99, pages 295-310. Springer-Verlag, 1999. LNCS no. 1592.]]

[12]

S. Goldwasser and S. Micali. Probabilistic encryption. J. Comp. Sys. Sci, 28(1):270-299, 1984.]]

[13]

M. Rirt and K. Sako. Efficient receipt-free voting based on homomorphic encryption. In B. Preneel, editor, EU- ROCRYPT '00, pages 539-556. Springer-Verlag, 2000. LNCS no. 1807.]]

[14]

M. Jakobsson. Personal homepage. http://www.markus-jakobsson.com.]]

[15]

M. Jakobsson. A practical mix. In K. Nyberg, editor, EUROCRYPT '98, pages 448-461. Springer-Verlag, 1998. LNCS No. 1403.]]

[16]

M. Jakobsson. Flash mixing. In PODC '99, pages 83- 89. ACM, 1999.]]

Digital Library

[17]

M. Jakobsson and A. Juels. Millimix: Mixing in small batches, 1999. DIMACS Technical Report 99-33.]]

Digital Library

[18]

M. Jakobsson and A. Juels. Mix and match: Secure function evaluation via ciphertexts. In T. Okamoto, editor, ASIACRYPT '00, pages 162-177, 2000. LNCS No. 1976.]]

Digital Library

[19]

M. Jakobsson and D. M'Rafihi. Mix-based electronic payments. In E. Tavares S and H.Meijer, editors, SAC '98, pages 157-173. Springer-Verlag, 1998. LNOS no. 1556.]]

Digital Library

[20]

A. Juels. Personal homepage. http://www.ari-j uels.com.]]

[21]

A. Juels. Targeted advertising and privacy too. In D. Nhe, editor, RSA Conference Cryptographers' Track, 2001. To appear.]]

Digital Library

[22]

M. Luby. Pseudorandomness and Cryptographic Applications. Princeton Univ. Press, 1996.]]

Digital Library

[23]

N. Lynch. Distributed Algorithms. Morgan KaufIwnn, 1995.]]

Digital Library

[24]

M. Mitomo and K. Kurosawa. Attack for flash mix. In T. Okamoto, editor, ASIACRYPT '00, pages 192-204, 2000. LNCS No. 1976.]]

Digital Library

[25]

W. Ogata, K. Kurosawa, K. Sako, and K. Takatani. Fault tolerant anonymous channel. In Proc. ICICS '97, pages 440-444, 1997. LNCS No. 1334.]]

Digital Library

[26]

M. Ohkubo and M. Abe. A length-invariant hybrid mix. In T. Okamoto, editor, ASIACRYPT '00, pages 178-191, 2000. LNCS No. 1976.]]

Digital Library

[27]

C. Park, K. Itoh, and K. Kurosawa. All/nothing election scheme and anonymous channel. In T. Helleseth, editor, EUROCRYPT '93, pages 248-259. Springer- Verlag, 1993. LNCS No. 765.]]

Digital Library

[28]

A. Pfitzmann and B. Pfitzmarm. How to break the direct RSA-implementation of MiXes. In J.-J. Quisquater and J. Vandewalle, editors, EUROCRYPT '89, pages 373-381. Springer-Verlag, 1989. LNCS No. 434.]]

Digital Library

[29]

A. Pfitzmann, B. Pfitzmann, and M. Waidner. ISDN-MIXes: Untraceable communication with very small bandwidth overhead. In Info. Security, Proc. IFIP/Sec'91, pages 245-258, 1991.]]

[30]

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, EUROCRYPT '95. Springer-Verlag, 1995. LNCS No. 921.]]

[31]

P. Syverson, D. Goldschlag, and M. Reed. Anonymous connections and onion routing. In Proc. of 18th Annual Symposium on Security and Privacy, pages 44 - 54. IEEE Press, 1997.]]

Digital Library

Cited By

López-García DPérez Torreglosa JVera DSánchez-Raya M(2024)Binary-Tree-Fed Mixnet: An Efficient Symmetric Encryption SolutionApplied Sciences10.3390/app1403096614:3(966)Online publication date: 23-Jan-2024
https://doi.org/10.3390/app14030966
Naikoo FAhmad KBin Ahmad K(2022)Anonymity-Enabled Communication Channels: Attacks and Defense Methods2022 3rd International Conference for Emerging Technology (INCET)10.1109/INCET54531.2022.9824020(1-6)Online publication date: 27-May-2022
https://doi.org/10.1109/INCET54531.2022.9824020
Naikoo FAhmad KAhmad K(2022)Anonymity-Enabled Mix Network: Owing to Techniques and Proof of correctness2022 International Conference on Computing, Communication, and Intelligent Systems (ICCCIS)10.1109/ICCCIS56430.2022.10037727(176-181)Online publication date: 4-Nov-2022
https://doi.org/10.1109/ICCCIS56430.2022.10037727
Show More Cited By

Index Terms

An optimally robust hybrid mix network

Recommendations

A Length-Invariant Hybrid Mix
ASIACRYPT '00: Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology

This paper presents a secure and flexible Mix-net that has the following properties; it efficiently handles long plaintexts that exceed the modulus size of underlying public-key encryption as well as very short ones (length-flexible), input ciphertext ...
Reputable mix networks
PET'04: Proceedings of the 4th international conference on Privacy Enhancing Technologies

We define a new type of mix network that offers a reduced form of robustness: the mixnet can prove that every message it outputs corresponds to an input submitted by a player without revealing which input (for honest players). We call mixnets with this ...
An efficient publicly verifiable mix-net for long inputs
FC'06: Proceedings of the 10th international conference on Financial Cryptography and Data Security

We propose here the first efficient publicly verifiable hybrid mix-net. Previous publicly verifiable mix-net was only efficient for short ciphertexts and was not suitable for mixing long messages. Previous hybrid mix-net can mix long messages but did ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing

August 2001

323 pages

ISBN:1581133839

DOI:10.1145/383962

Chairmen:
Ajay Kshemkalyani
Univ. of Illinois at Chicago, Chicago
,
Nir Shavit
Tel-Aviv Univ.; and Sun Labs.

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC01

Sponsor:

PODC01: 20th Annual ACM Symposium on Principles of Distributed Computing

Rhode Island, Newport, USA

Acceptance Rates

PODC '01 Paper Acceptance Rate 39 of 118 submissions, 33%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
553
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

López-García DPérez Torreglosa JVera DSánchez-Raya M(2024)Binary-Tree-Fed Mixnet: An Efficient Symmetric Encryption SolutionApplied Sciences10.3390/app1403096614:3(966)Online publication date: 23-Jan-2024
https://doi.org/10.3390/app14030966
Naikoo FAhmad KBin Ahmad K(2022)Anonymity-Enabled Communication Channels: Attacks and Defense Methods2022 3rd International Conference for Emerging Technology (INCET)10.1109/INCET54531.2022.9824020(1-6)Online publication date: 27-May-2022
https://doi.org/10.1109/INCET54531.2022.9824020
Naikoo FAhmad KAhmad K(2022)Anonymity-Enabled Mix Network: Owing to Techniques and Proof of correctness2022 International Conference on Computing, Communication, and Intelligent Systems (ICCCIS)10.1109/ICCCIS56430.2022.10037727(176-181)Online publication date: 4-Nov-2022
https://doi.org/10.1109/ICCCIS56430.2022.10037727
Aslam STošić AMrissa M(2021)Secure and Privacy-Aware Blockchain Design: Requirements, Challenges and SolutionsJournal of Cybersecurity and Privacy10.3390/jcp10100091:1(164-194)Online publication date: 14-Mar-2021
https://doi.org/10.3390/jcp1010009
Ahmad KKamal A(2021)Mix Networks: Existing Scenarios and Future Directions on Security and PrivacyRecent Patents on Engineering10.2174/187221211466619122312561914:3(310-323)Online publication date: 19-Jan-2021
https://doi.org/10.2174/1872212114666191223125619
Liu CWu ZChen C(2019)How to design the faultless bribery and coercion prevention electronic voting scheme2019 International Conference on Intelligent Computing and its Emerging Applications (ICEA)10.1109/ICEA.2019.8858289(39-44)Online publication date: Aug-2019
https://doi.org/10.1109/ICEA.2019.8858289
Li LHuang CFu S(2017)A CCA-secure Verifiable Mix-Net2017 International Conference on Networking and Network Applications (NaNA)10.1109/NaNA.2017.57(239-245)Online publication date: Oct-2017
https://doi.org/10.1109/NaNA.2017.57
Chaum DDas DJavani FKate AKrasnova ADe Ruiter JSherman A(2017)cMix: Mixing with Minimal Real-Time Asymmetric Cryptographic OperationsApplied Cryptography and Network Security10.1007/978-3-319-61204-1_28(557-578)Online publication date: 26-Jun-2017
https://doi.org/10.1007/978-3-319-61204-1_28
Fanti GViswanath P(2016)Algorithmic advances in anonymous communication over networks2016 Annual Conference on Information Science and Systems (CISS)10.1109/CISS.2016.7460490(133-138)Online publication date: Mar-2016
https://doi.org/10.1109/CISS.2016.7460490
Cabarcas-Jaramillo D(2015)EL VOTO ELECTRÓNICO Y RETOS CRIPTOGRÁFICOS RELACIONADOSRevista de la Facultad de Ciencias10.15446/rev.fac.cienc.v4n2.516774:2(83-102)Online publication date: 1-Jul-2015
https://doi.org/10.15446/rev.fac.cienc.v4n2.51677
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents