Paper 2019/747

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

Rupeng Yang, Man Ho Au, Zhenfei Zhang, Qiuliang Xu, Zuoxia Yu, and William Whyte

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in Crypto 2019
Keywords
LatticeZero-Knowledge Argument
Contact author(s)
orbbyrp @ gmail com
History
2019-06-25: received
Short URL
https://ia.cr/2019/747
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/747,
      author = {Rupeng Yang and Man Ho Au and Zhenfei Zhang and Qiuliang Xu and Zuoxia Yu and William Whyte},
      title = {Efficient Lattice-Based Zero-Knowledge Arguments with Standard Soundness: Construction and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2019/747},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/747}},
      url = {https://eprint.iacr.org/2019/747}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.