UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Linear Algebra with Sub-linear Zero-Knowledge Arguments

Groth, J; (2009) Linear Algebra with Sub-linear Zero-Knowledge Arguments. In: Halevi, S, (ed.) ADVANCES IN CRYPTOLOGY - CRYPTO 2009. (pp. 192 - 208). SPRINGER-VERLAG BERLIN

Full text not available from this repository.

Abstract

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(root 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(root N) group elements and a computation complexity of O(N) multiplications for both the prover and the verifier.

Type: Proceedings paper
Title: Linear Algebra with Sub-linear Zero-Knowledge Arguments
Event: 29th Annual International Cryptology Conference
Location: Santa Barbara, CA
Dates: 2009-08-16 - 2009-08-20
ISBN-13: 978-3-642-03355-1
Keywords: Sub-linear size zero-knowledge arguments, public-coin special honest verifier zero-knowledge, Pedersen commitments, linear algebra, circuit satisfiability, SHUFFLE
UCL classification: UCL > School of BEAMS > Faculty of Engineering Science
UCL > School of BEAMS > Faculty of Engineering Science > Computer Science
URI: http://discovery.ucl.ac.uk/id/eprint/149227
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item