Efficient Arguments without Short PCPs.
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky:
Abstract:
Current constructions of efficient argument systems combine a short (polynomial size) PCP with a
cryptographic hashing technique. We suggest an alternative approach for this problem that allows to
simplify the underlying PCP machinery using a stronger cryptographic technique.
More concretely, we present a direct method for compiling an exponentially long PCP which is
succinctly described by a linear oracle function \pi : F^n to F into an argument system in which the
verifier sends to the prover O(n) encrypted field elements and receives O(1) encryptions in return. This
compiler can be based on an arbitrary homomorphic encryption scheme. Applying our general compiler
to the exponential size Hadamard code based PCP of Arora et al. (JACM 1998) yields a simple argument
system for NP in which the communication from the prover to the verifier only includes a constant
number of short encryptions.
The main tool we use is a new cryptographic primitive which allows to efficiently commit to a linear
function and later open the output of the function on an arbitrary vector. Our efficient implementation of
this primitive is independently motivated by cryptographic applications.
comment: IEEE Conference on Computational Complexity 2007: 278-291
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |