Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Zero-Knowledge Proofs via Polynomial Representations
verfasst von : Giovanni Di Crescenzo, Vadym Fedyukovych
Erschienen in: Mathematical Foundations of Computer Science 2012
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
Under the existence of commitment schemes with homomorphic properties, we construct a constant-round zero-knowledge proof system for an
$\mathcal NP$
-complete language that requires a number of commitments that is
sublinear
in the size of the (best known) witness verification predicate. The overall communication complexity improves upon best known results for the specific
$\mathcal NP$
-complete language [1,2] and results that could be obtained using zero-knowledge proof systems for the entire
$\mathcal NP$
class (most notably, [3,2,4]). Perhaps of independent interest, our techniques build a
proof system
after reducing the theorem to be proved to statements among low-degree polynomials over large fields and using Schwartz-Zippel lemma to prove polynomial identities among committed values.