Abstract
We introduce a robust and efficient mix-network for exponentiation, and use it to obtain a threshold decryption mix-network for ElGamal encrypted messages, in which mix servers do not need to trust each other for the correctness of the result. If a subset of mix servers cheat, they will be caught with an overwhelming probability, and the decryption can restart after replacing them, in a fashion that is transparent to the participants providing the input to be decrypted. As long as a quorum is not controlled by an adversary, the privacy of the mix is guaranteed. Our solution is proved to be secure if a commonly used assumption, the Decision Diffie-Hellman assumption, holds.
Of possible independent interest are two new methods that we introduce: blinded destructive robustness, a type of destructive robustness with protection against leaks of secret information; and repetition robustness, a method for obtaining robustness for some distributed vector computations. Here, two or more calculations of the same equation are performed, where the different computations are made independent by the use of blinding and permutation. The resulting vectors are then unblinded, sorted and compared to each other. This allows us to detect cheating (resulting in inequality of the vectors).
Also of possible independent interest is a modular extension to the El-Gamal encryption scheme, making the resulting scheme non-malleable in the random oracle model. This is done by interpreting part of the ciphertext as a public key, and sign the ciphertext using the corresponding secret key.
Chapter PDF
Similar content being viewed by others
References
M. Abe, “Universally Verifiable Mix-net with Verification Work Independent of the Number of Mix-centers,” Eurocrypt '98.
M. Bellare, A. Desai, D. Pointcheval, P. Rogaway, “Plaintext Awareness, Non-Malleability, and Chosen Ciphertext Security: Implications and Separations,” manuscript.
M. Bellare, J. Garay, T. Rabin, “Batch Verification with Applications to Program Checking and Cryptography,” Eurocrypt '98
D. Chaum, “Untraceable electronic mail, return addresses, and digital pseudonyms,” Communications of the ACM, ACM 1981, pp. 84–88 “Undeniable Signatures,”
D. Chaum, H. Van Antwerpen, Crypto '89, pp. 212–216
D. Chaum, “Zero-Knowledge Undeniable Signatures,” Eurocrypt '90, pp. 458–464
R. Cramer, V. Shoup, “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack,” available at www.cs.wisc.edu/ shoup.
A. De Santis, Y. Desmedt, Y. Frankel, and M. Yung, “How to Share a Function Securely,” STOC '94, pp. 522–533
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
E. Gabber, P. Gibbons, Y. Matias, A. Mayer, “How to make personalized web browsing simple, secure, and anonymous,” Financial Cryptography '97
S. Goldwasser and S. Micali, “Probabilistic Encryption,” J. Comp. Sys. Sci. 28, pp 270–299, 1984.
C. Gulcu, G. Tsudik, “Mixing email with babel,” ISOC Symposium on Network and Distributed System Security, 1996.
A. Herzberg, S. Jarecki, H. Krawczyk, M. Yung, “Proactive Secret Sharing, or How to Cope with Perpetual Leakage,” Crypto '95, pp. 339–352
A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk, M. Yung, “Proactive Public Key and Signature Systems,” Proceedings of the 4th ACM Conference on Computer and Communications Security, 1997, pp. 100–110
M. Michels, P. Horster, “Some remarks on a receipt free and universally verifiable Mix-Type Voting scheme,” Asiacrypt '96, pp. 125–132
M. Jakobsson, K. Sako, R. Impagliazzo, “Designated Verifier Proofs and Their Applications,” Eurocrypt '96, pp. 143–154
M. Jakobsson, M. Yung, “Distributed ‘Magic Ink’ Signatures,” Eurocrypt '97, pp. 450–464
M. Jakobsson, “Privacy vs. Anonymity,” Ph.D. Thesis, University of California, San Diego, 1997. Available at http://www.bell-labs.com/markusj/.
NIST FIPS PUB XX, “Digital Signature Standard,” National Institute of Standards and Technology, U.S. Department of Commerce, Draft, 1 Feb. 1993
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.
A. Pfitzmann, B. Pfitzmann, M. Waidner, “ISDN-MIXes: Untraceable Communication with Very Small Bandwidth Overhead,” Information Security, Proc. IFIP/Sec'91, Mai 1991, Brighton, D. T. Lindsay, W. L. Price (eds.), North-Holland, Amsterdam 1991, 245–258.
D. Pointcheval and J. Stern, “Security Proofs for Signature Schemes,” Advances in Cryptology — Proceedings of Eurocrypt '96, pp. 387–398.
M. Reiter, A. Rubin, “Crowds: Anonymous Web Transactions,” Manuscript at www.research.att.com/projects/crowds/
K. Sako, J. Kilian, “Receipt-Free Mix-Type Voting Scheme,” Eurocrypt '95, pp. 393–403
C. P. Schnorr, “Efficient Signature Generation for Smart Cards,” Advances in Cryptology — Proceedings of Crypto '89, pp. 239–252
A. Shamir, “How to Share a Secret,” Communications of the ACM, Vol. 22, 1979, pp. 612–613
P. Syverson, D. Goldschlag, M. Reed, “Anonymous connections and onion routing,” IEEE Symposium on Security and Privacy, 1997.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jakobsson, M. (1998). A practical mix. In: Nyberg, K. (eds) Advances in Cryptology — EUROCRYPT'98. EUROCRYPT 1998. Lecture Notes in Computer Science, vol 1403. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054145
Download citation
DOI: https://doi.org/10.1007/BFb0054145
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64518-4
Online ISBN: 978-3-540-69795-4
eBook Packages: Springer Book Archive