International Association for Cryptologic Research

International Association
for Cryptologic Research


Qiuliang Xu

Affiliation: Shandong University


Efficient Lattice-Based Zero-Knowledge Arguments with Standard Soundness: Construction and Applications 📺
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.
Multiparty Computation for Modulo Reduction without Bit-Decomposition and a Generalization to Bit-Decomposition
Chao Ning Qiuliang Xu
Bit-decomposition, which is proposed by Damg{\aa}rd \emph{et al.}, is a powerful tool for multi-party computation (MPC). Given a sharing of secret \emph{a}, it allows the parties to compute the sharings of the bits of \emph{a} in constant rounds. With the help of bit-decomposition, constant rounds protocols for various MPC problems can be constructed. However, bit-decomposition is relatively expensive, so constructing protocols for MPC problems without relying on bit-decomposition is a meaningful work. In multi-party computation, it remains an open problem whether the "modulo reduction" problem can be solved in constant rounds without bit-decomposition. In this paper, we propose a protocol for (public) modulo reduction without relying on bit-decomposition. This protocol achieves constant round complexity and linear communication complexity. Moreover, we also propose a generalization to bit-decomposition which can, in constant rounds, convert the sharing of secret \emph{a} into the sharings of the "digits" of \emph{a}, along with the sharings of the bits of every "digit". The "digits" can be base-\emph{m} for any $m\geq2$. Obviously, when \emph{m} is a power of 2, this (generalized) protocol is just the original bit-decomposition protocol.