×

On publicly-accountable zero-knowledge and small shuffle arguments. (English) Zbl 1480.94025

Garay, Juan A. (ed.), Public-key cryptography – PKC 2021. 24th IACR international conference on practice and theory of public key cryptography, virtual event, May 10–13, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 12711, 618-648 (2021).
Summary: Constructing interactive zero-knowledge arguments from simple assumptions with small communication complexity and good computational efficiency is an important, but difficult problem. In this work, we study interactive arguments with noticeable soundness error in their full generality and for the specific purpose of constructing concretely efficient shuffle arguments.
To counterbalance the effects of a larger soundness error, we show how to transform such three-move arguments into publicly-accountable ones which allow the verifier to convince third parties of detected misbehavior by a cheating prover. This may be particularly interesting for applications where a malicious prover has to balance the profits it can make from cheating successfully and the losses it suffers from being caught.
We construct interactive, public-coin, zero-knowledge arguments with noticeable soundness error for proving that a target vector of commitments is a pseudorandom permutation of a source vector. Our arguments do not rely on any trusted setup and only require the existence of collision-resistant hash functions. The communication complexity of our arguments is independent of the length of the shuffled vector. For a soundness error of \(2^{-5}=1/32\), the communication cost is 153 bytes without and 992 bytes with public accountability, meaning that our arguments are shorter than shuffle arguments realized using Bulletproofs [B. Bünz et al., “Bulletproofs: short proofs for confidential transactions and more”, in: 2018 IEEE Symposium on Security and Privacy. 315–334 (2018)] and even competitive in size with SNARKs, despite only relying on simple assumptions.
For the entire collection see [Zbl 1476.94004].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abe, M.; Nyberg, K., Universally verifiable mix-net with verification work independent of the number of mix-servers, Advances in Cryptology — EUROCRYPT’98, 437-447 (1998), Heidelberg: Springer, Heidelberg · Zbl 0929.68062 · doi:10.1007/BFb0054144
[2] Abe, M.; Lam, K-Y; Okamoto, E.; Xing, C., Mix-networks on permutation networks, Advances in Cryptology - ASIACRYPT’99, 258-273 (1999), Heidelberg: Springer, Heidelberg · Zbl 0959.68516 · doi:10.1007/978-3-540-48000-6_21
[3] Abe, M.; Hoshino, F.; Kim, K., Remarks on mix-network based on permutation networks, Public Key Cryptography, 317-324 (2001), Heidelberg: Springer, Heidelberg · Zbl 0977.68031 · doi:10.1007/3-540-44586-2_23
[4] Advanced Encryption Standard (AES). National Institute of Standards and Technology (NIST), FIPS PUB 197, U.S. Department of Commerce, November 2001
[5] Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: ACM CCS 2017, pp. 2087-2104 (2017)
[6] Asharov, G.; Orlandi, C.; Wang, X.; Sako, K., Calling out cheaters: covert security with public verifiability, Advances in Cryptology - ASIACRYPT 2012, 681-698 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94022 · doi:10.1007/978-3-642-34961-4_41
[7] Aumann, Y.; Lindell, Y.; Vadhan, SP, Security against covert adversaries: efficient protocols for realistic adversaries, Theory of Cryptography, 137-156 (2007), Heidelberg: Springer, Heidelberg · Zbl 1129.94010 · doi:10.1007/978-3-540-70936-7_8
[8] Aviram, N.; Gellert, K.; Jager, T.; Ishai, Y.; Rijmen, V., Session resumption protocols and efficient forward security for TLS 1.3 0-RTT, Advances in Cryptology - EUROCRYPT 2019, 117-150 (2019), Cham: Springer, Cham · Zbl 1428.94056 · doi:10.1007/978-3-030-17656-3_5
[9] Bayer, S.; Groth, J.; Pointcheval, D.; Johansson, T., Efficient zero-knowledge argument for correctness of a shuffle, Advances in Cryptology - EUROCRYPT 2012, 263-280 (2012), Heidelberg: Springer, Heidelberg · Zbl 1297.94045 · doi:10.1007/978-3-642-29011-4_17
[10] Bentov, I.; Kumaresan, R.; Miller, A.; Takagi, T.; Peyrin, T., Instantaneous decentralized poker, Advances in Cryptology - ASIACRYPT 2017, 410-440 (2017), Cham: Springer, Cham · Zbl 1409.94863 · doi:10.1007/978-3-319-70697-9_15
[11] Bernstein, D.J.: Chacha, a variant of salsa20. In: Workshop Record of SASC, vol. 8, pp. 3-5 (2008)
[12] Boneh, D.; Waters, B.; Sako, K.; Sarkar, P., Constrained pseudorandom functions and their applications, Advances in Cryptology - ASIACRYPT 2013, 280-300 (2013), Heidelberg: Springer, Heidelberg · Zbl 1314.94057 · doi:10.1007/978-3-642-42045-0_15
[13] Bowe, S.: BLS12-381: New zk-SNARK Elliptic Curve Construction, March 2017. https://electriccoin.co/blog/new-snark-curve/
[14] Boyle, E., et al.: Efficient two-round OT extension and silent non-interactive secure computation. In: ACM CCS 2019, pp. 291-308 (2019)
[15] Boyle, E.; Goldwasser, S.; Ivan, I.; Krawczyk, H., Functional signatures and pseudorandom functions, Public-Key Cryptography - PKC 2014, 501-519 (2014), Heidelberg: Springer, Heidelberg · Zbl 1290.94145 · doi:10.1007/978-3-642-54631-0_29
[16] Brakerski, Z.; Vaikuntanathan, V.; Dodis, Y.; Nielsen, JB, Constrained key-homomorphic PRFS from standard lattice assumptions, Theory of Cryptography, 1-30 (2015), Heidelberg: Springer, Heidelberg · Zbl 1379.94032 · doi:10.1007/978-3-662-46497-7_1
[17] Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, pp. 315-334 (2018)
[18] Chaum, D., Untraceable electronic mail, return addresses, and digital pseudonyms, Commun. ACM, 24, 2, 84-88 (1981) · doi:10.1145/358549.358563
[19] Chung, K-M; Lui, E.; Pass, R.; Dodis, Y.; Nielsen, JB, From weak to strong zero-knowledge and applications, Theory of Cryptography, 66-92 (2015), Heidelberg: Springer, Heidelberg · Zbl 1354.94026 · doi:10.1007/978-3-662-46494-6_4
[20] Dagher, G.G., Bünz, B., Bonneau, J., Clark, J., Boneh, D.: Provisions: Privacy-preserving proofs of solvency for bitcoin exchanges. In: ACM CCS 2015, pp. 720-731 (2015)
[21] Damgård, I.; Orlandi, C.; Simkin, M.; Micciancio, D.; Ristenpart, T., Black-box transformations from passive to covert security with public verifiability, Advances in Cryptology - CRYPTO 2020, 647-676 (2020), Cham: Springer, Cham · Zbl 1525.68007 · doi:10.1007/978-3-030-56880-1_23
[22] Fauzi, P.; Meiklejohn, S.; Mercer, R.; Orlandi, C.; Galbraith, SD; Moriai, S., Quisquis: a new design for anonymous cryptocurrencies, Advances in Cryptology - ASIACRYPT 2019, 649-678 (2019), Cham: Springer, Cham · Zbl 1456.94076 · doi:10.1007/978-3-030-34578-5_23
[23] Fiat, A.; Shamir, A.; Odlyzko, AM, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology — CRYPTO’ 86, 186-194 (1987), Heidelberg: Springer, Heidelberg · Zbl 0636.94012 · doi:10.1007/3-540-47721-7_12
[24] Fisher, RA; Yates, F., Statistical Tables for Biological, Agricultural and Medical Research (1949), Edinburgh: Oliver and Boyd, Edinburgh · JFM 64.1202.02
[25] Furukawa, J.; Sako, K.; Kilian, J., An efficient scheme for proving a shuffle, Advances in Cryptology — CRYPTO 2001, 368-387 (2001), Heidelberg: Springer, Heidelberg · Zbl 1003.94522 · doi:10.1007/3-540-44647-8_22
[26] Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: 43rd ACM STOC, pp. 99-108 (2011) · Zbl 1288.94063
[27] Goldreich, O., A uniform-complexity treatment of encryption and zero-knowledge, J. Cryptol., 6, 1, 21-53 (1993) · Zbl 0795.68069 · doi:10.1007/BF02620230
[28] Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions (extended abstract). In: 25th FOCS, pp. 464-479 (1984)
[29] Goldreich, O.; Kahan, A., How to construct constant-round zero-knowledge proof systems for NP, J. Cryptol., 9, 3, 167-189 (1996) · Zbl 0855.68085 · doi:10.1007/BF00208001
[30] Groth, J.; Desmedt, YG, A verifiable secret shuffe of homomorphic encryptions, Public Key Cryptography — PKC 2003, 145-160 (2003), Heidelberg: Springer, Heidelberg · Zbl 1033.94527 · doi:10.1007/3-540-36288-6_11
[31] Groth, J.; Halevi, S., Linear algebra with sub-linear zero-knowledge arguments, Advances in Cryptology - CRYPTO 2009, 192-208 (2009), Heidelberg: Springer, Heidelberg · Zbl 1252.94068 · doi:10.1007/978-3-642-03356-8_12
[32] Groth, J.; Fischlin, M.; Coron, J-S, On the size of pairing-based non-interactive arguments, Advances in Cryptology - EUROCRYPT 2016, 305-326 (2016), Heidelberg: Springer, Heidelberg · Zbl 1369.94539 · doi:10.1007/978-3-662-49896-5_11
[33] Groth, J.; Ishai, Y.; Smart, N., Sub-linear zero-knowledge argument for correctness of a shuffle, Advances in Cryptology - EUROCRYPT 2008, 379-396 (2008), Heidelberg: Springer, Heidelberg · Zbl 1149.94319 · doi:10.1007/978-3-540-78967-3_22
[34] Groth, J.; Lu, S.; Okamoto, T.; Wang, X., Verifiable shuffle of large size ciphertexts, Public Key Cryptography - PKC 2007, 377-392 (2007), Heidelberg: Springer, Heidelberg · Zbl 1161.94401 · doi:10.1007/978-3-540-71677-8_25
[35] Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: 39th ACM STOC, pp. 21-30 (2007) · Zbl 1232.68044
[36] Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: ACM CCS 2013, pp. 669-684 (2013)
[37] Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: 24th ACM STOC, pp. 723-732 (1992)
[38] Kwon, A.; Lazar, D.; Devadas, S.; Ford, B., Riffle: an efficient communication system with strong anonymity, PoPETs, 2016, 2, 115-134 (2016)
[39] Lindell, Y.: How to simulate it - A tutorial on the simulation proof technique. Cryptology ePrint Archive, Report 2016/046 (2016). http://eprint.iacr.org/2016/046
[40] Micali, S.: CS proofs (extended abstracts). In: 35th FOCS, pp. 436-453 (1994)
[41] Micciancio, D.; Sorrell, J.; Moriai, S.; Wang, H., Simpler statistically sender private oblivious transfer from ideals of cyclotomic integers, Advances in Cryptology - ASIACRYPT 2020, 381-407 (2020), Cham: Springer, Cham · Zbl 1511.94137 · doi:10.1007/978-3-030-64834-3_13
[42] Neff, C.A.: A verifiable secret shuffle and its application to e-voting. In: ACM CCS 2001, pp. 116-125 (2001)
[43] Pedersen, TP; Feigenbaum, J., Non-interactive and information-theoretic secure verifiable secret sharing, Advances in Cryptology — CRYPTO ’91, 129-140 (1992), Heidelberg: Springer, Heidelberg · Zbl 0763.94015 · doi:10.1007/3-540-46766-1_9
[44] Peikert, C.; Vaikuntanathan, V.; Waters, B.; Wagner, D., A framework for efficient and composable oblivious transfer, Advances in Cryptology - CRYPTO 2008, 554-571 (2008), Heidelberg: Springer, Heidelberg · Zbl 1183.94046 · doi:10.1007/978-3-540-85174-5_31
[45] Sako, K.; Kilian, J.; Guillou, LC; Quisquater, J-J, Receipt-free mix-type voting scheme, Advances in Cryptology — EUROCRYPT ’95, 393-403 (1995), Heidelberg: Springer, Heidelberg · Zbl 0973.94525 · doi:10.1007/3-540-49264-X_32
[46] Secure Hash Standard (SHS). National Institute of Standards and Technology, NIST FIPS PUB 180-4, U.S. Department of Commerce, August 2015
[47] SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. National Institute of Standards and Technology, NIST FIPS PUB 202, U.S. Department of Commerce, Aug 2015
[48] de Valence, H., Grigg, J., Tankersley, G., Valsorda, F., Isis Lovecruft, M.H.: The ristretto255 and decaf448 groups. IETF CFRG Internet Draft (2020)
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.