Article

Succinct non-interactive arguments via linear interactive proofs

Authors:

Alessandro Chiesa,

Rafail OstrovskyAuthors Info & Claims

TCC'13: Proceedings of the 10th theory of cryptography conference on Theory of Cryptography

Pages 315 - 333

https://doi.org/10.1007/978-3-642-36594-2_18

Published: 03 March 2013 Publication History

Abstract

Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays researches have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation.

A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O(1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have 'escaped the hegemony' of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments.

References

[1]

Aiello, W., Bhatt, S., Ostrovsky, R., Rajagopalan, S. R.: Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP. In: Welzl, E., Montanari, U., Rolim, J. D. P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 463-474. Springer, Heidelberg (2000)

Digital Library

[2]

Applebaum, B., Ishai, Y., Kushilevitz, E.: From Secrecy to Soundness: Efficient Verification via Secure Computation. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P. G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 152-163. Springer, Heidelberg (2010)

Digital Library

[3]

Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the ACM 45(3), 501-555 (1998); Preliminary version in FOCS 1992

Digital Library

[4]

Bitansky, N., Chiesa, A.: Succinct arguments from multi-prover interactive proofs and their efficiency benefits. In: Safavi-Naini, R. (ed.) CRYPTO 2012. LNCS, vol. 7417, pp. 255-272. Springer, Heidelberg (2012)

[5]

Brassard, G., Chaum, D., Crépeau, C.: Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences 37(2), 156-189 (1988)

Digital Library

[6]

Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS 2012), pp. 326-349 (2012)

Digital Library

[7]

Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKs and proof-carrying data. Cryptology ePrint Archive, Report 2012/095 (2012)

[8]

Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Omer, P.: Succinct non-interactive arguments via linear interactive proofs. Cryptology ePrint Archive, Report 2012 (2012)

[9]

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 1991), pp. 21-32 (1991)

Digital Library

[10]

Barak, B., Goldreich Universal, O.: arguments and their applications. SIAM Journal on Computing 38(5), 1661-1694 (2008); Preliminary version appeared in CCC 2002

Digital Library

[11]

Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable Delegation of Computation over Large Datasets. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 111-131. Springer, Heidelberg (2011)

Digital Library

[12]

Boppana, R. B., Håstad, J., Zachos, S.: Does co-NP have short interactive proofs? Information Processing Letters 25(2), 127-132 (1987)

Digital Library

[13]

Bellare, M., Palacio, A.: The Knowledge-of-Exponent Assumptions and 3- Round Zero-Knowledge Protocols. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 273-289. Springer, Heidelberg (2004)

[14]

Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concreteefficiency threshold of probabilistically-checkable proofs. Electronic Colloquium on Computational Complexity, TR12-045 (2012)

[15]

Ben-Sasson, E., Harsha, P., Lachish, O., Matsliah, A.: Sound 3-Query PCPPs are Long. ACM Transactions on Computation Theory 1(2), 7:1- 7:49 (2009); Preliminary version appeared in: Aceto, L., Damgård, I., Goldberg, L. A., Halldórsson, M. M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 686-697. Springer, Heidelberg (2008)

Digital Library

[16]

Boneh, D., Segev, G., Waters, B.: Targeted malleability: Homomorphic encryption for restricted computations. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS 1912), pp. 350-366 (2012)

Digital Library

[17]

Bogdanov, A., Viola, E.: Pseudorandom bits for polynomials. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 41-51 (2007)

Digital Library

[18]

Chung, K.-M., Kalai, Y., Vadhan, S.: Improved Delegation of Computation Using Fully Homomorphic Encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483-501. Springer, Heidelberg (2010)

Digital Library

[19]

Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS 2012), pp. 90-112 (2012)

Digital Library

[20]

Canetti, R., Riva, B., Rothblum, G. N.: Two 1-round protocols for delegation of computation. Cryptology ePrint Archive, Report 2011/518 (2011)

[21]

Cormode, G., Thaler, J., Yi, K.: Verifying computations with streaming interactive proofs. Proceedings of the VLDB Endowment 5(1), 25-36 (2011)

Digital Library

[22]

Damgård, I. B.: Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 445-456. Springer, Heidelberg (1992)

Digital Library

[23]

Di Crescenzo, G., Lipmaa, H.: Succinct NP Proofs from an Extractability Assumption. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds.) CiE 2008. LNCS, vol. 5028, pp. 175-185. Springer, Heidelberg (2008)

Digital Library

[24]

Damgård, I. B., Faust, S., Hazay, C.: Secure Two-Party Computation with Low Communication. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 54-74. Springer, Heidelberg (2012)

Digital Library

[25]

Dwork, C., Feige, U., Kilian, J., Naor, M., Safra, M.: Low Communication 2-Prover Zero-Knowledge Proofs for NP. In: Brickell, E. F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 215-227. Springer, Heidelberg (1993)

Digital Library

[26]

Dvir, Z., Gabizon, A., Wigderson, A.: Extractors and rank extractors for polynomial sources. Computational Complexity 18(1), 1-58 (2009)

Digital Library

[27]

Dwork, C., Langberg, M., Naor, M., Nissim, K., Reingold, O.: Succinct NP proofs and spooky interactions (December 2004), www.openu.ac.il/home/mikel/papers/spooky.ps

[28]

El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31(4), 469-472 (1985)

Digital Library

[29]

Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. Cryptology ePrint Archive, Report 2012/281 (2012)

[30]

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-194. Springer, Heidelberg (1987)

Digital Library

[31]

Gennaro, R., Gentry, C., Parno, B.: Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465-482. Springer, Heidelberg (2010)

Digital Library

[32]

Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. Cryptology ePrint Archive, Report 2012/215 (2012)

[33]

Goldreich, O., Håstad, J.: On the complexity of interactive proofs with bounded communication. Information Processing Letters 67(4), 205-214 (1998)

Digital Library

[34]

Goldwasser, S., Kalai, Y. T., Rothblum, G. N.: Delegating computation: Interactive proofs for Muggles. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC 2008), pp. 113-122 (2008)

Digital Library

[35]

Goldwasser, S., Lin, H., Rubinstein, A.: Delegation of computation without rejection problem from designated verifier CS-proofs. Cryptology ePrint Archive, Report 2011/456 (2011)

[36]

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186-208 (1989); Preliminary version appeared in STOC 1985

Digital Library

[37]

Gabizon, A., Raz, R.: Deterministic extractors for affine sources over large fields. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 407-418 (2005)

Digital Library

[38]

Groth, J.: Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321- 340. Springer, Heidelberg (2010)

[39]

Goldreich, O., Vadhan, S., Wigderson, A.: On interactive proofs with a laconic prover. Computational Complexity 11(1/2), 1-53 (2002)

Digital Library

[40]

Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011), pp. 99-108 (2011)

Digital Library

[41]

Håstad, J., Khot, S.: Query efficient PCPs with perfect completeness. Theory of Computing 1(1), 119-148 (2005)

[42]

Hada, S., Tanaka, T.: On the Existence of 3-Round Zero-Knowledge Protocols. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 408- 423. Springer, Heidelberg (1998)

Digital Library

[43]

Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs. In: Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity (CCC 2007), pp. 278-291 (2007)

Digital Library

[44]

Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC 1992), pp. 723-732 (1992)

Digital Library

[45]

Kalai, Y. T., Raz, R.: Interactive PCP. In: Aceto, L., Damgård, I., Goldberg, L. A., Halldórsson, M. M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 536-547. Springer, Heidelberg (2008)

Digital Library

[46]

Kalai, Y. T., Raz, R.: Probabilistically Checkable Arguments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 143-159. Springer, Heidelberg (2009)

Digital Library

[47]

Lipmaa, H.: Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 169-189. Springer, Heidelberg (2012)

Digital Library

[48]

Lyubashevsky, V., Peikert, C., Regev, O.: On Ideal Lattices and Learning with Errors over Rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1-23. Springer, Heidelberg (2010)

Digital Library

[49]

Meir, O.: Combinatorial PCPs with short proofs. In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC 2012) (2012)

Digital Library

[50]

Micali, S.: Computationally sound proofs. SIAM Journal on Computing 30(4), 1253-1298 (2000); Preliminary version appeared in FOCS 1994

Digital Library

[51]

Mie, T.: Polylogarithmic two-round argument systems. Journal of Mathematical Cryptology 2(4), 343-363 (2008)

[52]

Naor, M.: On Cryptographic Assumptions and Challenges. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 96-109. Springer, Heidelberg (2003)

[53]

Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990), pp. 213-223 (1990)

Digital Library

[54]

Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223-238. Springer, Heidelberg (1999)

Digital Library

[55]

Petit, C., Quisquater, J.-J.: On Polynomial Systems Arising from a Weil Descent. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 451-466. Springer, Heidelberg (2012)

Digital Library

[56]

Setty, S., Braun, B., Vu, V., Blumberg, A. J., Parno, B., Walfish, M.: Resolving the conflict between generality and plausibility in verified computation. Cryptology ePrint Archive, Report 2012/622 (2012)

[57]

Setty, S., Blumberg, A. J., Walfish, M.: Toward practical and unconditional verification of remote computations. In: Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems (HotOS 2013), p. 29 (2011)

Digital Library

[58]

Shamir, A.: IP = PSPACE. Journal of the ACM 39(4), 869-877 (1992)

Digital Library

[59]

Setty, S., McPherson, M., Blumberg, A. J., Walfish, M.: Making argument systems for outsourced computation practical (sometimes). In: Proceedings of the 2012 Network and Distributed System Security Symposium (NDSS 2012) (2012)

[60]

Setty, S., Vu, V., Panpalia, N., Braun, B., Blumberg, A. J., Walfish, M.: Taking proof-based verified computation a few steps closer to practicality. In: Proceedings of the 21st USENIX Security Symposium (Security 2012) (2012)

Digital Library

[61]

Valiant, L. G.: Graph-Theoretic Arguments in Low-Level Complexity. In: Gruska, J. (ed.) MFCS 1977. LNCS, vol. 53, pp. 162-176. Springer, Heidelberg (1977)

[62]

Wee, H.: On round-efficient argument systems. In: Caires, L., Italiano, G. F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 140-152. Springer, Heidelberg (2005)

Digital Library

Cited By

Spathoulas GKatsika AKavallieratos G(2024)Privacy Preserving and Verifiable Outsourcing of AI Processing for Cyber-Physical SystemsInformation and Communications Security10.1007/978-981-97-8798-2_15(292-311)Online publication date: 27-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-8798-2_15
Choudhuri AGoel AHegde AJain A(2024)Homomorphic Secret Sharing with Verifiable EvaluationTheory of Cryptography10.1007/978-3-031-78023-3_20(614-650)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78023-3_20
Rotem LSegev GYogev E(2024)From One-Time to Two-Round Reusable Multi-signatures Without Nested ForkingTheory of Cryptography10.1007/978-3-031-78020-2_13(371-399)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78020-2_13
Show More Cited By

Succinct non-interactive arguments via linear interactive proofs
1. Security and privacy
2. Theory of computation

Recommendations

From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
ITCS '12: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference

The existence of succinct non-interactive arguments for NP (i.e., non-interactive computationally-sound proofs where the verifier's work is essentially independent of the complexity of the NP nondeterministic verifier) has been an intriguing question ...
Succinct Non-Interactive Arguments via Linear Interactive Proofs
Abstract
Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays, researchers have ...
Separating succinct non-interactive arguments from all falsifiable assumptions
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

An argument system for NP is succinct, if its communication complexity is polylogarithmic the instance and witness sizes. The seminal works of Kilian '92 and Micali '94 show that such arguments can be constructed under standard cryptographic hardness ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

TCC'13: Proceedings of the 10th theory of cryptography conference on Theory of Cryptography

March 2013

722 pages

ISBN:9783642365935

Editor:
Amit Sahai
UCLA, 3731E Boelter Hall, Los Angeles, CA

Sponsors

IACR: International Association for Cryptologic Research

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 03 March 2013

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

106
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Spathoulas GKatsika AKavallieratos G(2024)Privacy Preserving and Verifiable Outsourcing of AI Processing for Cyber-Physical SystemsInformation and Communications Security10.1007/978-981-97-8798-2_15(292-311)Online publication date: 27-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-8798-2_15
Choudhuri AGoel AHegde AJain A(2024)Homomorphic Secret Sharing with Verifiable EvaluationTheory of Cryptography10.1007/978-3-031-78023-3_20(614-650)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78023-3_20
Rotem LSegev GYogev E(2024)From One-Time to Two-Round Reusable Multi-signatures Without Nested ForkingTheory of Cryptography10.1007/978-3-031-78020-2_13(371-399)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78020-2_13
Waters BZhandry M(2024)Adaptive Security in SNARGs via iO and Lossy FunctionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68403-6_3(72-104)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68403-6_3
Mathialagan SPeters SVaikuntanathan V(2024)Adaptively Sound Zero-Knowledge SNARKs for UPAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68403-6_2(38-71)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68403-6_2
Albrecht MFenzi GLapiha ONguyen N(2024)SLAP: Succinct Lattice-Based Polynomial Commitments from Standard AssumptionsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58754-2_4(90-119)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58754-2_4
Freitag CPaneth OPass R(2024)Public-Coin, Complexity-Preserving, Succinct Arguments of Knowledge for NP from Collision-ResistanceAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_5(112-141)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58737-5_5
Wee HWu D(2024)Succinct Functional Commitments for Circuits from k-Advances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58723-8_10(280-310)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58723-8_10
Dutta MGanesh CJawalkar N(2024)Succinct Verification of Compressed Sigma Protocols in the Updatable SRS SettingPublic-Key Cryptography – PKC 202410.1007/978-3-031-57722-2_10(305-336)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57722-2_10
Baum CDittmer SScholl PWang X(2023)Sok: vector OLE-based zero-knowledge protocolsDesigns, Codes and Cryptography10.1007/s10623-023-01292-891:11(3527-3561)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1007/s10623-023-01292-8
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten