2014 | OriginalPaper | Buchkapitel
Probabilistically Checkable Proofs of Proximity with Zero-Knowledge
verfasst von : Yuval Ishai, Mor Weiss
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A probabilistically Checkable Proof (PCP) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form “
x
∈
L
” by querying only few bits of the proof. A
PCP of proximity
(PCPP) has the additional feature of allowing the verifier to query only few bits of the
input
x
, where if the input is accepted then the verifier is guaranteed that (with high probability) the input is
close
to some
x
′ ∈
L
.
Motivated by their usefulness for sublinear-communication cryptography, we initiate the study of a natural zero-knowledge variant of PCPP (ZKPCPP), where the view of any verifier making a bounded number of queries can be efficiently simulated by making the same number of queries to
the input oracle alone
. This new notion provides a useful extension of the standard notion of zero-knowledge PCPs. We obtain two types of results.
Constructions.
We obtain the first constructions of query-efficient ZKPCPPs via a general transformation which combines standard query-efficient PCPPs with protocols for secure multiparty computation. As a byproduct, our construction provides a conceptually simpler alternative to a previous construction of honest-verifier zero-knowledge PCPs due to Dwork et al. (Crypto ’92).
Applications.
We motivate the notion of ZKPCPPs by applying it towards sublinear-communication implementations of commit-and-prove functionalities. Concretely, we present the first sublinear-communication commit-and-prove protocols which make a
black-box
use of a collision-resistant hash function, and the first such multiparty protocols which offer
information-theoretic
security in the presence of an honest majority.