Efficient Zero-Knowledge Argument for Correctness of a Shuffle

1. 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)

   Chapter  Google Scholar 

2. Abe, M.: Mix-Networks on Permutation Networks. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 258–273. Springer, Heidelberg (1999)

   Chapter  Google Scholar 

3. Abe, M., Hoshino, F.: Remarks on Mix-Network Based on Permutation Networks. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 317–324. Springer, Heidelberg (2001)

   Chapter  Google Scholar 

4. Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 24(2), 84–88 (1981)

   Article  Google Scholar 

5. Cook, S.: On the minimum computation time of functions. PhD thesis, Department of Mathematics, Harvard University (1966), http://cr.yp.to/bib/1966/cook.html

6. Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex fourier series. Math. Comp. 19, 297–301 (1965)

   Article  MathSciNet  MATH  Google Scholar 

7. Furukawa, J.: Efficient and verifiable shuffling and shuffle-decryption. IEICE Transactions 88-A(1), 172–188 (2005)

   Google Scholar 

8. Furukawa, J., Miyauchi, H., Mori, K., Obana, S., Sako, K.: An Implementation of a Universally Verifiable Electronic Voting Scheme Based on Shuffling. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 16–30. Springer, Heidelberg (2003)

   Chapter  Google Scholar 

9. Furukawa, J., Mori, K., Sako, K.: An Implementation of a Mix-Net Based Network Voting Scheme and Its Use in a Private Organization. In: Chaum, D., Jakobsson, M., Rivest, R.L., Ryan, P.Y.A., Benaloh, J., Kutylowski, M., Adida, B. (eds.) Towards Trustworthy Elections. LNCS, vol. 6000, pp. 141–154. Springer, Heidelberg (2010)

   Chapter  Google Scholar 

10. Furukawa, J., Sako, K.: An Efficient Scheme for Proving a Shuffle. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 368–387. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

11. Garay, J., MacKenzie, P., Yang, K.: Strengthening zero-knowledge protocols using signatures. J. Cryptology 19(2), 169–209 (2006)

    Article  MathSciNet  MATH  Google Scholar 

12. Groth, J.: Honest verifier zero-knowledge arguments applied. Dissertation Series DS-04-3, BRICS, 2004. PhD thesis. xii+119 (2004)

    Google Scholar 

13. Groth, J.: Linear Algebra with Sub-linear Zero-Knowledge Arguments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 192–208. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

14. Groth, J.: A verifiable secret shuffle of homomorphic encryptions. J. Cryptology 23(4), 546–579 (2010)

    Article  MathSciNet  MATH  Google Scholar 

15. Groth, J., Ishai, Y.: Sub-linear Zero-Knowledge Argument for Correctness of a Shuffle. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 379–396. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

16. Groth, J., Lu, S.: Verifiable Shuffle of Large Size Ciphertexts. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 377–392. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

17. Karatsuba, A., Ofman, Y.: Multiplication of multidigit numbers on automata. Soviet Physics Dokl. 7, 595–596 (1963)

    Google Scholar 

18. Lim, C.: Efficient multi-exponentiation and application to batch verification of digital signatures (2000), http://dasan.sejong.ac.kr/~chlim/pub/multiexp.ps

19. Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. J. Cryptology 16(3), 143–184 (2003)

    Article  MathSciNet  MATH  Google Scholar 

20. Neff, C.A.: A verifiable secret shuffle and its application to e-voting. In: ACM CCS, pp. 116–125 (2001)

    Google Scholar 

21. Neff, C.A.: Verifiable mixing (shuffling) of elgamal pairs (2003), http://people.csail.mit.edu/rivest/voting/papers/Neff-2004-04-21-ElGamalShuffles.pdf

22. Pedersen, T.P.: Non-interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)

    Google Scholar 

23. 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)

    Google Scholar 

24. Shoup, V.: Ntl library (2009), http://www.shoup.net/ntl/

25. Terelius, B., Wikström, D.: Proofs of Restricted Shuffles. In: Bernstein, D.J., Lange, T. (eds.) AFRICACRYPT 2010. LNCS, vol. 6055, pp. 100–113. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

26. Toom, A.: The complexity of a scheme of functional elements realizing the multiplication of integers (2000), http://www.de.ufpe.br/~toom/my_articles/engmat/MULT-E.PDF

27. Wikström, D.: The Security of a Mix-Center Based on a Semantically Secure Cryptosystem. In: Menezes, A., Sarkar, P. (eds.) INDOCRYPT 2002. LNCS, vol. 2551, pp. 368–381. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

28. Wikström, D.: A Commitment-Consistent Proof of a Shuffle. In: Boyd, C., González Nieto, J. (eds.) ACISP 2009. LNCS, vol. 5594, pp. 407–421. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

29. Wikström, D.: Verificatum (2010), http://www.verificatum.com/

Download references