Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Interactive Oracle Proof:
TR16-149 | 23rd September 2016
Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

A security analysis of Probabilistically Checkable Proofs

Comments: 1

Probabilistically Checkable Proofs (PCPs) [Babai et al. FOCS 90; Arora et al. JACM 98] can be used to construct asymptotically efficient cryptographic zero knowledge arguments of membership in any language in NEXP, with minimal communication complexity and computational effort on behalf of both prover and verifier [Babai et al. STOC ... more >>>

TR20-083 | 30th May 2020
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf

Proximity Gaps for Reed-Solomon Codes

Revisions: 3

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are $\delta$-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are $\delta$-close to the property. In particular, no set ... more >>>

TR21-180 | 21st December 2021
Noga Ron-Zewi, Ron Rothblum

Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input $x$ belongs to a language $L \in NP$, with communication that is much shorter than the $NP$ witness. Such arguments, which grew out of the theory literature, are now drawing ... more >>>

TR22-110 | 1st August 2022
Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves

Concretely efficient interactive oracle proofs (IOPs) are of interest due to their applications to scaling blockchains, their minimal security assumptions, and their potential future-proof resistance to quantum attacks.

Scalable IOPs, in which prover time scales quasilinearly with the computation size and verifier time scales poly-logarithmically with it, have been known ... more >>>

ISSN 1433-8092 | Imprint