International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Lattice-Based Zero-Knowledge Arguments with Standard Soundness: Construction and Applications

Authors:
Rupeng Yang
Man Ho Au
Zhenfei Zhang
Qiuliang Xu
Zuoxia Yu
William Whyte
Download:
DOI: 10.1007/978-3-030-26948-7_6 (login may be required)
Search ePrint
Search Google
Abstract: We provide new zero-knowledge argument of knowledge systems that work directly for a wide class of language, namely, ones involving the satisfiability of matrix-vector relations and integer relations commonly found in constructions of lattice-based cryptography. Prior to this work, practical arguments for lattice-based relations either have a constant soundness error (2/3), or consider a weaker form of soundness, namely, extraction only guarantees that the prover is in possession of a witness that “approximates” the actual witness. Our systems do not suffer from these limitations.The core of our new argument systems is an efficient zero-knowledge argument of knowledge of a solution to a system of linear equations, where variables of this solution satisfy a set of quadratic constraints. This argument enjoys standard soundness, a small soundness error (1/poly), and a complexity linear in the size of the solution. Using our core argument system, we construct highly efficient argument systems for a variety of statements relevant to lattices, including linear equations with short solutions and matrix-vector relations with hidden matrices.Based on our argument systems, we present several new constructions of common privacy-preserving primitives in the standard lattice setting, including a group signature, a ring signature, an electronic cash system, and a range proof protocol. Our new constructions are one to three orders of magnitude more efficient than the state of the art (in standard lattice). This illustrates the efficiency and expressiveness of our argument system.
Video from CRYPTO 2019
BibTeX
@article{crypto-2019-29859,
  title={Efficient Lattice-Based Zero-Knowledge Arguments with Standard Soundness: Construction and Applications},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11692},
  pages={147-175},
  doi={10.1007/978-3-030-26948-7_6},
  author={Rupeng Yang and Man Ho Au and Zhenfei Zhang and Qiuliang Xu and Zuoxia Yu and William Whyte},
  year=2019
}