[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1030083.1030113acmconferencesArticle/Chapter ViewAbstractPublication PagesccsConference Proceedingsconference-collections
Article

Parallel mixing

Published: 25 October 2004 Publication History

Abstract

Efforts to design faster synchronous mix networks have focused on reducing the computational cost of mixing per server. We propose a different approach: our reencryption mixnet allows servers to mix inputs in parallel. The result is a dramatic reduction in overall mixing time for moderate-to-large numbers of servers. As measured in the model we describe, for n inputs and $M$ servers our parallel re encryption mixnet produces output in time at most 2n -- and only around n assuming a majority of honest servers. In contrast, a traditional, sequential, synchronous re-encryption mixnet requires time Mn.
Parallel re-encryption mixnets offer security guarantees comparable to those of synchronous mixnets, and in many cases only a slightly weaker guarantee of privacy. Our proposed construction is applicable to many recently proposed re-encryption mixnets, such as those of Furukawa and Sako, Neff, Jakobsson et al., and Golle and Boneh. In practice, parallel mixnets promise a potentially substantial time saving in applications such as anonymous electronic elections.

References

[1]
M. Abe. Mix-networks on permutation networks. In ASIACRYPT '99, pages 258--273.]]
[2]
M. Abe and F. Hoshino. Remarks on mix-network based on permutation networks. In PKC '01, pages 317--324.]]
[3]
C. Cachin, K. Kursawe, and V. Shoup. Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography (extended abstract). In PODC '00, pages 123--132.]]
[4]
D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24(2):84--88, 1981.]]
[5]
G. Danezis, R. Dingledine, and N. Mathewson. Mixminion: Design of a type III anonymous remailer protocol. In IEEE Symposium on Security and Privacy '03, pages 2--15.]]
[6]
Y. Desmedt and K. Kurosawa. How to break a practical mix and design a new one. In EUROCRYPT'00, pages 557--572.]]
[7]
R. Dingledine, V. Shmatikov, and P. Syverson. Synchronous batching: From cascades to free routes. In Privacy Enhancing Technologies '04. To appear.]]
[8]
J. Furukawa, H. Miyauchi, K. Mori, S. Obana, and K. Sako. An implementation of a universally verifiable electronic voting scheme based on shuffling. In Financial Cryptography '02, pages 16--30.]]
[9]
J. Furukawa and K. Sako. An efficient scheme for proving a shuffle. In CRYPTO '01, pages 368--387.]]
[10]
P. Golle and D. Boneh. Almost entirely correct mixing with applications to voting. In ACM CCS '02, pages 68--77.]]
[11]
M. Jakobsson. Flash mixing. In PODC '99, pages 83--89.]]
[12]
M. Jakobsson. A practical mix. In EUROCRYPT '98, pages 448--461.]]
[13]
M. Jakobsson and A. Juels. An optimally robust hybrid mix network. In PODC '01, pages 284--292.]]
[14]
M. Jakobsson and A. Juels. Millimix: Mixing in small batches, 1999. DIMACS Technical Report 99-33.]]
[15]
M. Jakobsson, A. Juels, and R. Rivest. Making mix nets robust for electronic voting by randomized partial checking. In USENIX'02, pages 339--353.]]
[16]
A. Kiayias and M. Yung. The vector-ballot e-voting approach. In Financial Cryptography '04, pages 72--89.]]
[17]
D. Knuth. The Art of Computer Programming, Vol 3: Sorting and Searching. Addison-Wesley, 1998.]]
[18]
N. Lynch. Distributed Algorithms. Morgan Kaufmann, 1995.]]
[19]
A. Ne. A verifiable secret shuffle and its application to e-voting. In ACM CCS '01, pages 116--125.]]
[20]
W. Ogata, K. Kurosawa, K. Sako, and K. Takatani. Fault tolerant anonymous channel. In ICICS '97, pages 440--444.]]
[21]
M. Ohkubo and M. Abe. A length-invariant hybrid mix. In ASIACRYPT '00, pages 178--191.]]
[22]
C. Racko and D. R. Simon. Cryptographic defense against traffic analysis. In ACM Symposium on Theory of Computing, pages 672--681, 1993.]]
[23]
A. Serjantov and G. Danezis. Towards an information theoretic metric for anonymity. In Privacy Enhancing Technologies '02, pages 41--53.]]
[24]
A. Waksman. A permutation network. JACM, 15(1):159--163, 1968.]]
[25]
M. Wright, M. Adler, B. N. Levine, and C. Shields. An analysis of the degradation of anonymous protocols. In NDSS '02, pages 39--50.]]

Cited By

View all
  • (2022)Toward Round-Efficient Verifiable Re-Encryption Mix-NetIEEE Access10.1109/ACCESS.2022.320296610(91397-91413)Online publication date: 2022
  • (2020)Hybrid Routing: Towards Resilient Routing in Anonymous Communication NetworksICC 2020 - 2020 IEEE International Conference on Communications (ICC)10.1109/ICC40277.2020.9149166(1-7)Online publication date: Jun-2020
  • (2018)KaraokeProceedings of the 13th USENIX conference on Operating Systems Design and Implementation10.5555/3291168.3291221(711-725)Online publication date: 8-Oct-2018
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
CCS '04: Proceedings of the 11th ACM conference on Computer and communications security
October 2004
376 pages
ISBN:1581139616
DOI:10.1145/1030083
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: 25 October 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. anonymity
  2. mixnet
  3. parallel execution
  4. permutation
  5. privacy

Qualifiers

  • Article

Conference

CCS04
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)12
  • Downloads (Last 6 weeks)1
Reflects downloads up to 26 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2022)Toward Round-Efficient Verifiable Re-Encryption Mix-NetIEEE Access10.1109/ACCESS.2022.320296610(91397-91413)Online publication date: 2022
  • (2020)Hybrid Routing: Towards Resilient Routing in Anonymous Communication NetworksICC 2020 - 2020 IEEE International Conference on Communications (ICC)10.1109/ICC40277.2020.9149166(1-7)Online publication date: Jun-2020
  • (2018)KaraokeProceedings of the 13th USENIX conference on Operating Systems Design and Implementation10.5555/3291168.3291221(711-725)Online publication date: 8-Oct-2018
  • (2018)A Universally Composable Framework for the Privacy of Email EcosystemsAdvances in Cryptology – ASIACRYPT 201810.1007/978-3-030-03332-3_8(191-221)Online publication date: 26-Oct-2018
  • (2017)StadiumProceedings of the 26th Symposium on Operating Systems Principles10.1145/3132747.3132783(423-440)Online publication date: 14-Oct-2017
  • (2017)AtomProceedings of the 26th Symposium on Operating Systems Principles10.1145/3132747.3132755(406-422)Online publication date: 14-Oct-2017
  • (2014)ReferencesAnonymous Communication Networks10.1201/b16756-8(183-190)Online publication date: 3-Apr-2014
  • (2013)Theory and Practice of Secure E-Voting SystemsTheory and Practice of Cryptography Solutions for Secure Information Systems10.4018/978-1-4666-4030-6.ch017(428-459)Online publication date: 2013
  • (2013)Equally contributory privacy-preserving k-means clustering over vertically partitioned dataInformation Systems10.1016/j.is.2012.06.00138:1(97-107)Online publication date: 1-Mar-2013
  • (2013)Round-Efficient Private Stable Matching from Additive Homomorphic EncryptionProceedings of the 16th International Conference on Information Security - Volume 780710.1007/978-3-319-27659-5_5(69-86)Online publication date: 13-Nov-2013
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media