Abstract
Two universally verifiable mix-net schemes that eliminate the cumbersome Cut-and-Choose method are presented. The construction is based on a permutation network composed of a network of ‘switches’ that transposes two inputs. For N inputs and t tolerable corrupt mix-servers, the schemes achieve \({\cal O}(t N \log N)\) efficiency in computation and communication while previous schemes require \({\cal O}(\kappa m N)\) for error probability 2 − κ and m mix-servers. The schemes suit small to middle-scale secret-ballot electronic elections. Moreover, one of the schemes enjoys less round complexity so that servers do not need to talk to other servers except their neighbors unless disruption occurs.
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
Abe, M.: Universally verifiable mix-net with verification work independent of the number of mix-servers. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 437–447. Springer, Heidelberg (1998)
Abe, M.: Robust threshold Cramer-Shoup cryptosystem. In: Proc. of the 1999 Symposium on Cryptography and Information Security. T1-1.3 (1999) (in Japanese)
Bellare, M., Garay, J.A., Rabin, T.: Fast batch verification for modular exponentiation and digital signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 236–250. Springer, Heidelberg (1998)
Canetti, R., Goldwasser, S.: An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 90–106. Springer, Heidelberg (1999)
Chaum, D.L.: Untraceable electronic mail, return address, and digital pseudonyms. Communications of the ACM 24, 84–88 (1981)
Chaum, D.L., Pedersen, T.P.: Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89–105. Springer, Heidelberg (1993)
Cramer, R., Damgärd, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–199. Springer, Heidelberg (1987)
Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 259–310. Springer, Heidelberg (1999)
Jakobsson, M.: A practical mix. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 448–461. Springer, Heidelberg (1998)
Jakobsson, M.: Flash mixing. In: PODC 1999 (1999)
Ogata, W., Kurosawa, K., Sako, K., Takatani, K.: Fault tolerant anonymous channel. In: Han, Y., Quing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 440–444. Springer, Heidelberg (1997)
Park, C., Itoh, K., Kurosawa, K.: Efficient anonymous channel and all/nothing election scheme. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 248–259. Springer, Heidelberg (1994)
Pedersen, T.P.: A threshold cryptosystem without a trusted party. In: Advances in Cryptology — EUROCRYPT 1991, pp. 522–526. Springer, Heidelberg (1991)
Sako, K., Kilian, J.: Receipt-free mix-type voting scheme — a practical solution to the implementation of a voting booth. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 393–403. Springer, Heidelberg (1995)
Tsiounis, Y., Yung, M.: On the security of El Gamal based encryption. In: Imai, H., Zheng, Y. (eds.) PKC 1998. LNCS, vol. 1431, pp. 117–134. Springer, Heidelberg (1998)
Waksman, A.: A permutation network. Journal of the Association for Computing Machinery 15(1), 159–163 (1968)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abe, M. (1999). Mix-Networks on Permutation Networks. In: Lam, KY., Okamoto, E., Xing, C. (eds) Advances in Cryptology - ASIACRYPT’99. ASIACRYPT 1999. Lecture Notes in Computer Science, vol 1716. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48000-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-48000-6_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66666-0
Online ISBN: 978-3-540-48000-6
eBook Packages: Springer Book Archive