Subquadratic SNARGs in the random oracle model. (English) Zbl 1485.94073
Malkin, Tal (ed.) et al., Advances in cryptology – CRYPTO 2021. 41st annual international cryptology conference, CRYPTO 2021, virtual event, August 16–20, 2021. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12825, 711-741 (2021).
Summary: In a seminal work, S. Micali [SIAM J. Comput. 30, No. 4, 1253–1298 (2000; Zbl 1009.68053)] gave the first succinct non-interactive argument (SNARG) in the random oracle model (ROM). The construction combines a PCP and a cryptographic commitment, and has several attractive features: it is plausibly post-quantum; it can be heuristically instantiated via lightweight cryptography; and it has a transparent (public-coin) parameter setup. However, it also has a significant drawback: a large argument size.
In this work, we provide a new construction that achieves a smaller argument size. This is the first progress on the Micali construction since it was introduced over 25 years ago.
A SNARG in the ROM is \((t,\mathsf{\epsilon })\)-secure if every \(t\)-query malicious prover can convince the verifier of a false statement with probability at most \(\mathsf{\epsilon } \). For \((t,\mathsf{\epsilon })\)-security, the argument size of all known SNARGs in the ROM (including Micali’s) is \(\tilde{O}((\log (t/\mathsf{\epsilon }))^2)\) bits, even if one were to rely on conjectured probabilistic proofs well beyond current techniques. In practice, these costs lead to SNARGs that are much larger than constructions based on other (pre-quantum and costly) tools. This has led many to believe that SNARGs in the ROM are inherently quadratic.
We show that this is not the case. We present a SNARG in the ROM with a sub-quadratic argument size: \( \tilde{O}(\log (t/\mathsf{\epsilon }) \cdot \log t)\). Our construction relies on a strong soundness notion for PCPs and a weak binding notion for commitments. We hope that our work paves the way for understanding if a linear argument size, that is \(O(\log (t/\mathsf{\epsilon }))\), is achievable in the ROM.
For the entire collection see [Zbl 1483.94004].
In this work, we provide a new construction that achieves a smaller argument size. This is the first progress on the Micali construction since it was introduced over 25 years ago.
A SNARG in the ROM is \((t,\mathsf{\epsilon })\)-secure if every \(t\)-query malicious prover can convince the verifier of a false statement with probability at most \(\mathsf{\epsilon } \). For \((t,\mathsf{\epsilon })\)-security, the argument size of all known SNARGs in the ROM (including Micali’s) is \(\tilde{O}((\log (t/\mathsf{\epsilon }))^2)\) bits, even if one were to rely on conjectured probabilistic proofs well beyond current techniques. In practice, these costs lead to SNARGs that are much larger than constructions based on other (pre-quantum and costly) tools. This has led many to believe that SNARGs in the ROM are inherently quadratic.
We show that this is not the case. We present a SNARG in the ROM with a sub-quadratic argument size: \( \tilde{O}(\log (t/\mathsf{\epsilon }) \cdot \log t)\). Our construction relies on a strong soundness notion for PCPs and a weak binding notion for commitments. We hope that our work paves the way for understanding if a linear argument size, that is \(O(\log (t/\mathsf{\epsilon }))\), is achievable in the ROM.
For the entire collection see [Zbl 1483.94004].
MSC:
| 94A60 | Cryptography |
Citations:
Zbl 1009.68053Software:
libiopReferences:
| [1] | Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501-555 (1998). Preliminary version in FOCS ’92 · Zbl 1065.68570 |
| [2] | Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70-122 (1998). Preliminary version in FOCS ’92 · Zbl 0903.68076 |
| [3] | Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: Proceedings of the 39th IEEE Symposium on Security and Privacy, S&P ’18, pp. 315-334 (2018) |
| [4] | Baum, C.; Bootle, J.; Cerulli, A.; del Pino, R.; Groth, J.; Lyubashevsky, V.; Shacham, H.; Boldyreva, A., Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits, Advances in Cryptology - CRYPTO 2018, 669-699 (2018), Cham: Springer, Cham · Zbl 1436.94040 · doi:10.1007/978-3-319-96881-0_23 |
| [5] | Ben-Sasson, E.; Bentov, I.; Horesh, Y.; Riabzev, M.; Boldyreva, A.; Micciancio, D., Scalable zero knowledge with no trusted setup, Advances in Cryptology - CRYPTO 2019, 701-732 (2019), Cham: Springer, Cham · Zbl 1509.94063 · doi:10.1007/978-3-030-26954-8_23 |
| [6] | Bootle, J.; Cerulli, A.; Chaidos, P.; Groth, J.; Petit, C.; Fischlin, M.; Coron, J-S, Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting, Advances in Cryptology - EUROCRYPT 2016, 327-357 (2016), Heidelberg: Springer, Heidelberg · Zbl 1369.94520 · doi:10.1007/978-3-662-49896-5_12 |
| [7] | Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from Bitcoin. In: Proceedings of the 2014 IEEE Symposium on Security and Privacy, SP ’14, pp. 459-474 (2014) |
| [8] | Bitansky, N.; Chiesa, A.; Ishai, Y.; Paneth, O.; Ostrovsky, R.; Sahai, A., Succinct non-interactive arguments via linear interactive proofs, Theory of Cryptography, 315-333 (2013), Heidelberg: Springer, Heidelberg · Zbl 1316.68056 · doi:10.1007/978-3-642-36594-2_18 |
| [9] | Ben-Sasson, E.; Chiesa, A.; Riabzev, M.; Spooner, N.; Virza, M.; Ward, NP; Ishai, Y.; Rijmen, V., Aurora: transparent succinct arguments for R1CS, Advances in Cryptology - EUROCRYPT 2019, 103-128 (2019), Cham: Springer, Cham · Zbl 1470.94079 · doi:10.1007/978-3-030-17653-2_4 |
| [10] | Ben-Sasson, E.; Chiesa, A.; Spooner, N.; Hirt, M.; Smith, A., Interactive oracle proofs, Theory of Cryptography, 31-60 (2016), Heidelberg: Springer, Heidelberg · Zbl 1397.94048 · doi:10.1007/978-3-662-53644-5_2 |
| [11] | Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC ’91, pp. 21-32 (1991) |
| [12] | Bünz, B.; Fisch, B.; Szepieniec, A.; Canteaut, A.; Ishai, Y., Transparent SNARKs from DARK compilers, Advances in Cryptology - EUROCRYPT 2020, 677-706 (2020), Cham: Springer, Cham · Zbl 07436935 · doi:10.1007/978-3-030-45721-1_24 |
| [13] | Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximations. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 93, pp. 294-304 (1993) · Zbl 1310.68083 |
| [14] | Boneh, D.; Ishai, Y.; Sahai, A.; Wu, DJ; Coron, J-S; Nielsen, JB, Lattice-based SNARGs and their application to more efficient obfuscation, Advances in Cryptology - EUROCRYPT 2017, 247-277 (2017), Cham: Springer, Cham · Zbl 1415.94412 · doi:10.1007/978-3-319-56617-7_9 |
| [15] | Boneh, D.; Ishai, Y.; Sahai, A.; Wu, DJ; Nielsen, JB; Rijmen, V., Quasi-optimal SNARGs via linear multi-prover interactive proofs, Advances in Cryptology - EUROCRYPT 2018, 222-255 (2018), Cham: Springer, Cham · Zbl 1415.94413 · doi:10.1007/978-3-319-78372-7_8 |
| [16] | Bellare, M., Rogaway, P., Spies, T.: The FFX mode of operation for format-preserving encryption. NIST Submission 20, 19 (2010) |
| [17] | Chiesa, A.; Manohar, P.; Spooner, N.; Hofheinz, D.; Rosen, A., Succinct arguments in the quantum random oracle model, Theory of Cryptography, 1-29 (2019), Cham: Springer, Cham · Zbl 1455.94140 · doi:10.1007/978-3-030-36033-7_1 |
| [18] | Chiesa, A.; Yogev, E.; Pass, R.; Pietrzak, K., Barriers for succinct arguments in the random oracle model, Theory of Cryptography, 47-76 (2020), Cham: Springer, Cham · Zbl 1485.94072 · doi:10.1007/978-3-030-64378-2_3 |
| [19] | Damgård, IB; Brassard, G., A design principle for hash functions, Advances in Cryptology — CRYPTO’ 89 Proceedings, 416-427 (1990), New York: Springer, New York · Zbl 0724.68029 · doi:10.1007/0-387-34805-0_39 |
| [20] | Dinur, I., Harsha, P., Kindler, G.: Polynomially low error PCPs with polyloglog n queries via modular composition. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing, STOC ’15, pp. 267-276 (2015) · Zbl 1321.68305 |
| [21] | Feige, U., Goldwasser, S., Lovász, L., Safra, S., Szegedy, M.: Approximating clique is almost NP-complete (preliminary version). In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, SFCS ’91, pp. 2-12 (1991) |
| [22] | 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 |
| [23] | Gennaro, R.; Gentry, C.; Parno, B.; Raykova, M.; Johansson, T.; Nguyen, PQ, Quadratic span programs and succinct NIZKs without PCPs, Advances in Cryptology - EUROCRYPT 2013, 626-645 (2013), Heidelberg: Springer, Heidelberg · Zbl 1300.94056 · doi:10.1007/978-3-642-38348-9_37 |
| [24] | Goldreich, O., Håstad, J.: On the complexity of interactive proofs with bounded communication. Inf. Process. Lett. 67(4), 205-214 (1998) · Zbl 1338.68104 |
| [25] | Groth, J.; Abe, M., Short pairing-based non-interactive zero-knowledge arguments, Advances in Cryptology - ASIACRYPT 2010, 321-340 (2010), Heidelberg: Springer, Heidelberg · Zbl 1253.94049 · doi:10.1007/978-3-642-17373-8_19 |
| [26] | Hoang, VT; Rogaway, P.; Rabin, T., On generalized feistel networks, Advances in Cryptology - CRYPTO 2010, 613-630 (2010), Heidelberg: Springer, Heidelberg · Zbl 1283.94068 · doi:10.1007/978-3-642-14623-7_33 |
| [27] | Ishai, Y., Mahmoody, M., Sahai, A., Xiao, D.: On zero-knowledge PCPs: Limitations, simplifications, and applications (2015). http://www.cs.virginia.edu/ mohammad/files/papers/ZKPCPs-Full.pdf |
| [28] | Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC ’92, pp. 723-732 (1992) |
| [29] | Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373-386 (1988) · Zbl 0644.94018 |
| [30] | Merkle, RC; Brassard, G., One way hash functions and DES, Advances in Cryptology — CRYPTO’ 89 Proceedings, 428-446 (1990), New York: Springer, New York · Zbl 1533.94049 · doi:10.1007/0-387-34805-0_40 |
| [31] | Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253-1298 (2000). Preliminary version appeared in FOCS ’94 · Zbl 1009.68053 |
| [32] | Naor, M., Reingold, O.: On the construction of pseudorandom permutations: Luby-Rackoff revisited. J. Cryptol. 12(1), 29-66 (1999) · Zbl 0936.94010 |
| [33] | Electric Coin Company. Zcash Cryptocurrency (2014). https://z.cash/ |
| [34] | Ethereum. ZK-Rollups. https://docs.ethhub.io/ethereum-roadmap/layer-2-scaling/zk-rollups/ |
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.
