Short Round Sub-Linear Zero-Knowledge Argument for Linear Algebraic Relations

Jae Hong SEO

doi:10.1587/transfun.E95.A.776

Short Round Sub-Linear Zero-Knowledge Argument for Linear Algebraic Relations

Jae Hong SEO

Full Text Views

0

Cite this

Summary :

Zero-knowledge arguments allows one party to prove that a statement is true, without leaking any other information than the truth of the statement. In many applications such as verifiable shuffle (as a practical application) and circuit satisfiability (as a theoretical application), zero-knowledge arguments for mathematical statements related to linear algebra are essentially used. Groth proposed (at CRYPTO 2009) an elegant methodology for zero-knowledge arguments for linear algebraic relations over finite fields. He obtained zero-knowledge arguments of the sub-linear size for linear algebra using reductions from linear algebraic relations to equations of the form z=x*'y, where x, y ∈ Fⁿ_p are committed vectors, z ∈ F_p is a committed element, and *': Fⁿ_pFⁿ_pF_p is a bilinear map. These reductions impose additional rounds on zero-knowledge arguments of the sub-linear size. The round complexity of interactive zero-knowledge arguments is an important measure along with communication and computational complexities. We focus on minimizing the round complexity of sub-linear zero-knowledge arguments for linear algebra. 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E95-A No.4 pp.776-789

Publication Date: 2012/04/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E95.A.776

Type of Manuscript: PAPER

Category: Cryptography and Information Security

Cite this

Copy

Jae Hong SEO, "Short Round Sub-Linear Zero-Knowledge Argument for Linear Algebraic Relations" in IEICE TRANSACTIONS on Fundamentals, vol. E95-A, no. 4, pp. 776-789, April 2012, doi: 10.1587/transfun.E95.A.776.
Abstract: Zero-knowledge arguments allows one party to prove that a statement is true, without leaking any other information than the truth of the statement. In many applications such as verifiable shuffle (as a practical application) and circuit satisfiability (as a theoretical application), zero-knowledge arguments for mathematical statements related to linear algebra are essentially used. Groth proposed (at CRYPTO 2009) an elegant methodology for zero-knowledge arguments for linear algebraic relations over finite fields. He obtained zero-knowledge arguments of the sub-linear size for linear algebra using reductions from linear algebraic relations to equations of the form z=x*'y, where x, y ∈ Fⁿ_p are committed vectors, z ∈ F_p is a committed element, and *': Fⁿ_pFⁿ_pF_p is a bilinear map. These reductions impose additional rounds on zero-knowledge arguments of the sub-linear size. The round complexity of interactive zero-knowledge arguments is an important measure along with communication and computational complexities. We focus on minimizing the round complexity of sub-linear zero-knowledge arguments for linear algebra. 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E95.A.776/_p

Copy

@ARTICLE{e95-a_4_776,
author={Jae Hong SEO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Short Round Sub-Linear Zero-Knowledge Argument for Linear Algebraic Relations},
year={2012},
volume={E95-A},
number={4},
pages={776-789},
abstract={Zero-knowledge arguments allows one party to prove that a statement is true, without leaking any other information than the truth of the statement. In many applications such as verifiable shuffle (as a practical application) and circuit satisfiability (as a theoretical application), zero-knowledge arguments for mathematical statements related to linear algebra are essentially used. Groth proposed (at CRYPTO 2009) an elegant methodology for zero-knowledge arguments for linear algebraic relations over finite fields. He obtained zero-knowledge arguments of the sub-linear size for linear algebra using reductions from linear algebraic relations to equations of the form z=x*'y, where x, y ∈ Fⁿ_p are committed vectors, z ∈ F_p is a committed element, and *': Fⁿ_pFⁿ_pF_p is a bilinear map. These reductions impose additional rounds on zero-knowledge arguments of the sub-linear size. The round complexity of interactive zero-knowledge arguments is an important measure along with communication and computational complexities. We focus on minimizing the round complexity of sub-linear zero-knowledge arguments for linear algebra. 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.},
keywords={},
doi={10.1587/transfun.E95.A.776},
ISSN={1745-1337},
month={April},}

Copy

TY - JOUR
TI - Short Round Sub-Linear Zero-Knowledge Argument for Linear Algebraic Relations
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 776
EP - 789
AU - Jae Hong SEO
PY - 2012
DO - 10.1587/transfun.E95.A.776
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E95-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2012
AB - Zero-knowledge arguments allows one party to prove that a statement is true, without leaking any other information than the truth of the statement. In many applications such as verifiable shuffle (as a practical application) and circuit satisfiability (as a theoretical application), zero-knowledge arguments for mathematical statements related to linear algebra are essentially used. Groth proposed (at CRYPTO 2009) an elegant methodology for zero-knowledge arguments for linear algebraic relations over finite fields. He obtained zero-knowledge arguments of the sub-linear size for linear algebra using reductions from linear algebraic relations to equations of the form z=x*'y, where x, y ∈ Fⁿ_p are committed vectors, z ∈ F_p is a committed element, and *': Fⁿ_pFⁿ_pF_p is a bilinear map. These reductions impose additional rounds on zero-knowledge arguments of the sub-linear size. The round complexity of interactive zero-knowledge arguments is an important measure along with communication and computational complexities. We focus on minimizing the round complexity of sub-linear zero-knowledge arguments for linear algebra. 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.
ER -