×

More efficient shuffle argument from unique factorization. (English) Zbl 1479.94201

Paterson, Kenneth G. (ed.), Topics in cryptology – CT-RSA 2021. Cryptographers’ track at the RSA conference 2021, virtual event, May 17–20, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12704, 252-275 (2021).
Summary: Efficient shuffle arguments are essential in mixnet-based e-voting solutions. B. Terelius and D. Wikström [Lect. Notes Comput. Sci. 6055, 100–113 (2010; Zbl 1284.94117)] (TW) proposed a 5-round shuffle argument based on unique factorization in polynomial rings. Their argument is available as the Verificatum software solution for real-world developers, and has been used in real-world elections. It is also the fastest non-patented shuffle argument. We will use the same basic idea as TW but significantly optimize their approach. We generalize the TW characterization of permutation matrices; this enables us to reduce the communication without adding too much to the computation. We make the TW shuffle argument computationally more efficient by using Groth’s coefficient-product argument [J. Groth, ibid. 2567, 145–160 (2002; Zbl 1033.94527)]. Additionally, we use batching techniques. The resulting shuffle argument is the fastest known \(\le 5\)-message shuffle argument, and, depending on the implementation, can be faster than Groth’s argument (the fastest 7-message shuffle argument).
For the entire collection see [Zbl 1476.94005].

MSC:

94A60 Cryptography
68M12 Network protocols
91B12 Voting theory

Software:

Verificatum
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bayer, S., Groth, J.: Efficient zero-knowledge argument for correctness of a shuffle. In: EUROCRYPT 2012. LNCS, vol. 7237, pp. 263-280 (2012) · Zbl 1297.94045
[2] Bellare, M., Garay, J.A., Rabin, T.: Batch verification with applications to cryptography and checking. In: LATIN 1998. LNCS, vol. 1380, pp. 170-191 (1998)
[3] Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: CRYPTO’92. LNCS, vol. 740, pp. 390-420 (1992) · Zbl 0823.94016
[4] Bellare, M.; Rogaway, P., Random oracles are practical: a paradigm for designing efficient protocols, ACM CCS, 93, 62-73 (1993)
[5] Bellare, M., Rogaway, P.: Minimizing the use of random oracles in authenticated encryption schemes. In: ICICS 97. LNCS, vol. 1334, pp. 1-16 (1997) · Zbl 0888.94009
[6] Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: 20th ACM STOC, pp. 103-112 (1986)
[7] Brands, S.: Rapid demonstration of linear relations connected by Boolean operators. In: EUROCRYPT’97. LNCS, vol. 1233, pp. 318-333 (1997)
[8] Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: 30th ACM STOC, pp. 209-218 (1988) · Zbl 1027.68603
[9] Chaum, D., Untraceable electronic mail, return addresses, and digital pseudonyms, Commun. ACM, 24, 2, 84-88 (1981) · doi:10.1145/358549.358563
[10] Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: CRYPTO’94. LNCS, vol. 839, pp. 174-187 (1994) · Zbl 0939.94546
[11] ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: CRYPTO’84. LNCS, vol. 196, pp. 10-18 (1984) · Zbl 1359.94590
[12] Fauzi, P., Lipmaa, H.: Efficient culpably sound NIZK shuffle argument without random oracles. In: CT-RSA 2016. LNCS, vol. 9610, pp. 200-216 (2016) · Zbl 1334.68057
[13] Fauzi, P., Lipmaa, H., Siim, J., Zajac, M.: An efficient pairing-based shuffle argument. In: ASIACRYPT 2017, Part II. LNCS, vol. 10625, pp. 97-127 (2017) · Zbl 1380.94088
[14] Fauzi, P., Lipmaa, H., Zajac, M.: A shuffle argument secure in the generic model. In: ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 841-872 (2016) · Zbl 1407.94105
[15] Fauzi, P., Meiklejohn, S., Mercer, R., Orlandi, C.: Quisquis: A new design for anonymous cryptocurrencies. In: ASIACRYPT 2019, Part I. LNCS, vol. 11921, pp. 649-678 (2019) · Zbl 1456.94076
[16] Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: CRYPTO’86. LNCS, vol. 263, pp. 186-194 (1986) · Zbl 0636.94012
[17] Furukawa, J.: Efficient and verifiable shuffling and shuffle-decryption. IEICE Trans. 88-A(1), 172-188 (2005)
[18] Furukawa, J., Sako, K.: An efficient scheme for proving a shuffle. In: CRYPTO 2001. LNCS, vol. 2139, pp. 368-387 (2001) · Zbl 1003.94522
[19] Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: 44th FOCS, pp. 102-115 (2003)
[20] Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: 17th ACM STOC, pp. 291-304 (1983) · Zbl 0900.94025
[21] Groth, J., A verifiable secret shuffle of homomorphic encryptions, J. Cryptol., 23, 4, 546-579 (2010) · Zbl 1201.94086 · doi:10.1007/s00145-010-9067-9
[22] Groth, J., Kohlweiss, M.: One-out-of-many proofs: Or how to leak a secret and spend a coin. In: EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 253-280 (2015) · Zbl 1371.94639
[23] Groth, J., Lu, S.: A non-interactive shuffle with pairing based verifiability. In: ASIACRYPT 2007. LNCS, vol. 4833, pp. 51-67 (2007) · Zbl 1153.94387
[24] Hungerford, T.W.: Algebra. 8 edn. Graduate Texts in Mathematics, vol. 73. Springer, New York (1980) · Zbl 0442.00002
[25] Khazaei, S., Moran, T., Wikström, D.: A mix-net from any CCA2 secure cryptosystem. In: ASIACRYPT 2012. LNCS, vol. 7658, pp. 607-625 (2012) · Zbl 1292.94091
[26] Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. In: CRYPTO 2001. LNCS, vol. 2139, pp. 171-189 (2001) · Zbl 1002.94521
[27] Lipmaa, H., Zhang, B.: A more efficient computationally sound non-interactive zero-knowledge shuffle argument. In: SCN 12. LNCS, vol. 7485, pp. 477-502 (2012) · Zbl 1351.94056
[28] Neff, CA, A verifiable secret shuffle and its application to e-voting, ACM CCS, 2001, 116-125 (2001)
[29] Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: CRYPTO’91. LNCS, vol. 576, pp. 129-140 (1991) · Zbl 0763.94015
[30] Schwartz, JT, Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 4, 701-717 (1980) · Zbl 0452.68050 · doi:10.1145/322217.322225
[31] Straus, EG, Addition chains of vectors, Amer. Math. Monthly, 70, 806-808 (1964)
[32] Terelius, B., Wikström, D.: Proofs of restricted shuffles. In: AFRICACRYPT 10. LNCS, vol. 6055, pp. 100-113 (2010) · Zbl 1284.94117
[33] Wikström, D.: A commitment-consistent proof of a shuffle. In: ACISP 2009. LNCS, vol. 5594, pp. 4007-421 (2009) · Zbl 1284.94125
[34] Wikström, D.: How to Implement a Stand-alone Verifier for the Verificatum Mix-Net. Version 1.4.1 (2015). http://www.verificatum.org
[35] Zippel, R.: Probabilistic Algorithms for Sparse Polynomials. In: EUROSM 1979. LNCS, vol. 72, pp. 216-226 (1979) · Zbl 0418.68040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.