History

Please fill in your query. A complete syntax description you will find on the General Help page.
Round-efficient sub-linear zero-knowledge arguments for linear algebra. (English)
Catalano, Dario (ed.) et al., Public key cryptography ‒ PKC 2011. 14th international conference on practice and theory in public key cryptography, Taormina, Italy, March 6‒9, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-19378-1/pbk). Lecture Notes in Computer Science 6571, 387-402 (2011).
Summary: The round complexity of interactive zero-knowledge arguments is an important measure along with communication and computational complexities. In the case of zero-knowledge arguments for linear algebraic relations over finite fields, Groth proposed (at CRYPTO 2009) an elegant methodology that achieves sub-linear communication overheads and low computational complexity. He obtained zero-knowledge arguments of sub-linear size for linear algebra using reductions from linear algebraic relations to equations of the form $z = x *^{\prime} y$, where $x$, $y \in \mathbb{F}_p^n$ are committed vectors, $z \in \mathbb{F}_p$ is a committed element, and $*’ : \mathbb{F}_p^n \times \mathbb{F}_p^n \rightarrow \mathbb{F}_p$ is a bilinear map. These reductions impose additional rounds on zero-knowledge arguments of sub-linear size. We focus on minimizing such additional rounds, and we reduce the rounds of sub-linear zero-knowledge arguments for linear algebraic relations as compared with Groth’s zero-knowledge arguments for the same relations. To reduce round complexity, we propose a general transformation from a $t$-round zero-knowledge argument, satisfying mild conditions, to $a (t - 2)$-round zero-knowledge argument; this transformation is of independent interest.