You are here

How To Break a Practical MIX and Design a New One

TitleHow To Break a Practical MIX and Design a New One
Publication TypeConference Paper
Year of Publication2000
AuthorsDesmedt, Y, Kurosawa, K
Conference NameProceedings of EUROCRYPT 2000
PublisherSpringer-Verlag, LNCS 1803
ISBN Number978-3-540-67517-4
Keywordsexistential-honesty, limited-open-verification, mix

A MIX net takes a list of ciphertexts (c 1, ..., c N) and outputs a permuted list of the plaintexts (m 1, ..., m N) without revealing the relationship between (c 1,..., c N) and (m 1, ...,m N). This paper first shows that the Jakobsson’s MIX net of Eurocrypt’98, which was believed to be resilient and very efficient, is broken. We next propose an efficient t-resilient MIX net with O(t 2) servers in which the cost of each MIX server is O(N). Two new concepts are introduced, existential-honesty and limited-open-verification. They will be useful for distributed computation in general.
A part of this research was done while the author visited the Tokyo Institute of Technology, March 4–19, 1999. He was then at the University of Wisconsin — Milwaukee.

PDF icon KB