A note on efficient zero-knowledge proofs and arguments (extended abstract)

By Joe Kilian. 1992

In this note, we present new zero-knowledge interactive proofs and arguments for languages in <italic>NP</italic>. To show that <italic>x ε L</italic>, with an error probability of at most 2<supscrpt>-<italic>k</italic></supscrpt>, our zero-knowledge proof system requires <italic>O</italic>(|<italic>x</italic>|<supscrpt><italic>c</italic><subscrpt>1</subscrpt></supscrpt>)+<italic>O</italic>(lg<supscrpt><italic>c</italic><subscrpt>2</subscrpt></supscrpt>|<italic>x</italic>|)<italic>k</italic> ideal bit commitments, where <italic>c</italic><subscrpt>1</subscrpt> and <italic>c</italic><subscrpt>2</subscrpt> depend only on <italic>L</italic>. This construction is the first in the ideal bit commitment model that achieves large values of <italic>k</italic> more efficiently than by running <italic>k</italic> independent iterations of the base interactive proof system. Under suitable complexity assumptions, we exhibit zero knowledge arguments that require <italic>O</italic>(lg<supscrpt>c</supscrpt>|<italic>x</italic>|<italic>kl</italic> bits of communication, where <italic>c</italic> depends only on <italic>L</italic>, and <italic>l</italic> is the security parameter for the prover. This is the first construction in which the total amount of communication can be less than that needed to transmit the <italic>NP</italic> witness. Our protocols are based on efficiently checkable proofs for <italic>NP</italic>[4].

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Geppetto: Versatile Verifiable Computation (2015, background): “Prior work on verifying computation focused on narrow classes of computation [32, 51], relied on physical-security assumptions [41, 47], assumed uncorrelated failures [19, 20], or achieved good asymptotics [2, 28, 30, 31, 33, 38, 44] but impractical concrete performance [46, 50].”
Verifying computations with state (2013, background): “Each constraint corresponds to a “register operation” (arithmetic, assignment, etc.), which provides an interpretation of our metric.”
Doubly-Efficient zkSNARKs Without Trusted Setup (2018, unknown): “builds non-interactive ZK arguments from short PCPs, following the seminal work of Kilian [62, 63] and Micali [73], the landmark result of Ben-Sasson and Sudan [17], and recent generalizations of PCPs [9, 14, 87].”
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, background): “All known PCP-based succinct argument constructions [61, 71, 5, 30, 22, 14, 29, 47] inherit these problem representations.”
Short Pairing-Based Non-interactive Zero-Knowledge Arguments (2010, methodology): “It is for instance possible to use the Fiat-Shamir heuristic to transform sub-linear size interactive public-coin zero-knowledge arguments [32] into sub-linear size non-interactive zero-knowledge arguments [35].”
Publicly verifiable delegation of large polynomials and matrix computations, with applications (2012, background): “However, in PCP-based schemes, the client must store the large data in order to verify the result, and therefore these solutions might not be applicable to our setting.”
Improved Delegation of Computation using Fully Homomorphic Encryption (2010, methodology): “In this model, Kilian [ Kil92 ] and Micali [Mic94] gave constant-round protocols with prover complexity poly(T, k) and verifier complexity poly(n, k, log T )( wherek is the security parameter), assuming the existence of collision-resistant functions.”
Recursive composition and bootstrapping for SNARKS and proof-carrying data (2013, background): “In particular, they provide strong solutions to the problem of veri.ably delegating computation.”
Taking Proof-Based Verified Computation a Few Steps Closer to Practicality (2012, background): “This paper describes a built system, called GINGER, that addresses these problems, thereby taking generalpurpose proof-based verified computation several steps closer to practicality.”
Batch codes and their applications (2004, methodology): “Note that the above reduction from -PIR to -PIR (using batch codes) cannot be directly applied for reducing -OT to -OT, since it allows the user to get bits of information (rather than ), and even these are not necessarily physical bits of . However, it is possible to obtain similar amortization for”
Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers (2010, methodology): “To avoid this complication, Kilian proposed the use of efficient arguments 3 [19,20] in which the prover sends the verifier a short commitm ent to the entire proof using a Merkle tree.”
Delegating computation: interactive proofs for muggles (2008, background): “This is the “heaviest” computation run by the verifier, and this final computation is independent of the circuit C; it can be done in quasi-linear time in the input length.”