2009 | OriginalPaper | Buchkapitel
Linear Algebra with Sub-linear Zero-Knowledge Arguments
verfasst von : Jens Groth
Erschienen in: Advances in Cryptology - CRYPTO 2009
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
We suggest practical sub-linear size zero-knowledge arguments for statements involving linear algebra. Given commitments to matrices over a finite field, we give a sub-linear size zero-knowledge argument that one committed matrix is the product of two other committed matrices. We also offer a sub-linear size zero-knowledge argument for a committed matrix being equal to the Hadamard product of two other committed matrices. Armed with these tools we can give many other sub-linear size zero-knowledge arguments, for instance for a committed matrix being upper or lower triangular, a committed matrix being the inverse of another committed matrix, or a committed matrix being a permutation of another committed matrix.
A special case of what can be proved using our techniques is the satisfiability of an arithmetic circuit with
N
gates. Our arithmetic circuit zero-knowledge argument has a communication complexity of
$O(\sqrt{N})$
group elements. We give both a constant round variant and an
O
(log
N
) round variant of our zero-knowledge argument; the latter has a computation complexity of
O
(
N
/log
N
) exponentiations for the prover and
O
(
N
) multiplications for the verifier making it efficient for the prover and very efficient for the verifier. In the case of a binary circuit consisting of NAND-gates we give a zero-knowledge argument of circuit satisfiability with a communication complexity of
$O(\sqrt{N})$
group elements and a computation complexity of
O
(
N
) multiplications for both the prover and the verifier.