Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cybersecurity

Proving multiplicative relations for lattice commitments in batch

Mengfan Wang, Guifang Huang, Dong Fang, Lei Hu

Published Jan 27, 2026• 0 citations
Publisher

Abstract

Abstract Lattice-based commitment schemes and their associated zero-knowledge proofs are essential building blocks for advanced lattice-based cryptographic protocols. In particular, proofs of algebraic relations among committed messages are widely used in privacy-preserving protocols such as range proofs. At CRYPTO 2020, Attema et al. proposed practical proofs for valid openings and multiplicative relations among committed values using the BDLOP commitment scheme. In their work, all commitments are generated using the same short randomness. In this paper, we consider a batch setting where commitments are generated using $$\ell$$ ℓ independent random vectors and present a batch valid opening proof. Our construction generalizes the approach of Baum et al. by supporting a larger challenge set and removing the requirement for invertible challenge differences. As a result, the proof size scales logarithmically with $$\ell$$ ℓ , rather than linearly. Furthermore, we introduce a product proof for committed messages with shared randomness across these $$\ell$$ ℓ commitment groups. Compared to the naive approach of applying Attema’s product proof once and repeating the opening proof $$\ell -1$$ ℓ - 1 times, our method achieves significantly better communication efficiency.

DOI
10.1186/s42400-025-00521-y

Related papers

Lattice-Based Commitment Scheme for Low Communication Costs

Hideaki Miyaji, Yuntao Wang, Atsuko Miyaji

Commitment schemes are cryptographic schemes that can be applied to zero-knowledge proof construction and blockchain construction. Recently, lattice-based cryptography has been intensively investigated due to the promising potential in quantum cryptography. Accordingly, commitment schemes based on lattice assumptions have been studied for practical applications. Notably, applications often require committing an arbitrary message with low communication costs, so commitment schemes must be satisfied with fewer length restrictions and fewer extensions to the messages. Several studies have been conducted to achieve the problem, including the study published by Baum et al. in 2018. However, the scheme in question still utilizes the message domain for extraneous purposes. We design a length-extension-free commitment scheme ComMWMin which the length of the message string is large relative to the length of the commitment string, improving on the commitment scheme of Baum et al. Furthermore, we prove that the hiding and binding properties of ComMWMare based on the hardness of the decisional search knapsack problem and extended search knapsack problems, respectively. Finally, we evaluate the computation costs of generating commitment value between ours and Baum et al.’s commitment scheme.

IEEE Access•Jan 1, 2024•2 citations

Efficient Zero-Knowledge Proofs for Commitments from Learning With Errors over Rings.

Fabrice Benhamouda, Stephan Krenn, Vadim Lyubashevsky +1 more

Abstract. We design an efficient commitment scheme, and companion zero-knowledge proofs of knowledge, based on the learning with errors over rings (RLWE) problem. In particular, for rings in which almost all elements have inverses, we construct a perfectly binding commitment scheme whose hiding property relies on the RLWE assumption. Our scheme maps elements from the ring (or equivalently, n elements from Fq) to a small constant number of ring elements. We then construct Σ-protocols for proving, in a zero-knowledge manner, knowledge of the message contained in a commitment. We are able to further extend our basic protocol to allow us to prove additive and multiplicative relations among committed values. Our protocols have a communication complexity of O(Mn log q) and achieve a negligible knowledge error in one run. Here M is the constant from a rejection sampling technique that we employ, and can be set close to 1 by adjusting other parameters. Previously known Σ-protocols for LWE-related languages either relied on “smudging ” out the error (which necessitates working over large fields, resulting in poor efficiency) or only achieved a noticeable or even constant knowledge error (thus requiring many repetitions of the protocol).

•Jan 1, 2014•0 citations

Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings

Fabrice Benhamouda, Stephan Krenn, Vadim Lyubashevsky +1 more

We extend a commitment scheme based on the learning with errors over rings ( $$\mathsf{RLWE}$$ ) problem, and present efficient companion zero-knowledge proofs of knowledge. Our scheme maps elements from the ring (or equivalently, n elements from $$\mathbb F_q$$ ) to a small constant number of ring elements. We then construct $$\varSigma $$ -protocols for proving, in a zero-knowledge manner, knowledge of the message contained in a commitment. We are able to further extend our basic protocol to allow us to prove additive and multiplicative relations among committed values. Our protocols have a communication complexity of $$\mathcal {O}(Mn\log q)$$ and achieve a negligible knowledge error in one run. Here M is the constant from a rejection sampling technique that we employ, and can be set close to 1 by adjusting other parameters. Previously known $$\varSigma $$ -protocols for LWE-related languages only achieved a noticeable or even constant knowledge error (thus requiring many repetitions of the protocol), or relied on “smudging” out the error (which necessitates working over large fields, resulting in poor efficiency).

Lecture notes in computer science•Jan 1, 2015•69 citations

Practical Lattice-Based Zero-Knowledge Proofs for Integer Relations

Vadim Lyubashevsky, Ngoc Khanh Nguyen, Gregor Seiler

We present a novel lattice-based zero-knowledge proof system for showing that (arbitrary-sized) committed integers satisfy additive and multiplicative relationships. The proof sizes of our schemes are between two to three orders of magnitude smaller than in the lattice proof system of Libert et al. (CRYPTO 2018) for the same relations. Because the proof sizes of our protocols grow linearly in the integer length, our proofs will eventually be longer than those produced by quantum-safe succinct proof systems for general circuits (e.g. Ligero, Aurora, etc.). But for relations between reasonably-sized integers (e.g. $512$-bit), our proofs still result in the smallest zero-knowledge proof system based on a quantum-safe assumption. Of equal importance, the run-time of our proof system is at least an order of magnitude faster than any other quantum-safe scheme.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 30, 2020•45 citations

Compressed Zero-Knowledge Proofs for Lattice-Based Accumulator

Shumin Si, Xiuhan Lin, Puwen Wei

Abstract The lattice-based cryptographic accumulators, which enable short zero-knowledge arguments of membership, have numerous applications in post-quantum privacy-preserving protocols. However, most efficient quantum-safe zero-knowledge arguments are PCP-based systems and rely on non-falsifiable assumptions. For non-PCP-based constructions using the state-of-the-art techniques on compressing lattice-based zero-knowledge proofs, the concrete size of the resulting proof for accumulators with $2^{32}$ members is at least 500 KB. In this paper, we propose a compact non-PCP zero-knowledge proof for the lattice-based Merkle-tree, which leads to an efficient post-quantum cryptographic accumulator. The complexity of our construction is logarithmic in $l\cdot n_{s}$, where $l$ and $n_{s}$ denote the depth of the underlying Merkle-tree and the size of a node, respectively, and the concrete size is only $143.7\ $KB when $l=32$. In particular, we provide an improved lattice-based Bulletproof with efficient knowledge extraction, which allows large challenge space but small soundness slack. Furthermore, the amortized technique can be applied to the Bulletproof without breaking the knowledge soundness due to our improved knowledge extraction. As a direct application, we present a practical lattice-based ring signature, which can achieve logarithmical signing/verifying computational complexity with the number of the ring, while the state-of-the-art constructions (CRYPTO 21) have linear computational complexity.

The Computer Journal•Mar 10, 2023•3 citations

Post-Quantum Zero-Knowledge Proofs and Applications

Ron Steinfeld

Lattice-based cryptography is one of the most promising candidates for designing post-quantum cryptographic algorithms that resist emerging quantum computing attacks. The recent NIST PQC standardization process is nearing its completion, with practical lattice-based algorithms for basic cryptographic functionalities (namely digital signature and public-key encryption) selected for standardization in the near future. However, practical lattice-based solutions for more advanced privacy-preserving protocols, in particular, Zero-Knowledge Proofs (ZKPs), have only emerged recently and are an active area of research. We discuss some recent developments in design and analysis of practical lattice-based post-quantum ZKPs and their applications. In particular, we review some challenges that arise in designing ZKPs in the lattice setting and some recent progress on efficient lattice-based Schnorr-like proofs for important relations, such as binary/range proofs, one-out-of-many proofs and rounding proofs [1, 2, 4]. We discuss applications and optimization of such proof systems as building blocks for practical advanced cryptographic protocols such as ring signatures and balance proofs for privacy-preserving cryptocurrency payment protocols [2, 3]. We also discuss our recent work on succinct designated-verifier ZKPs (DV-ZKSNARKS) for verifying correctness of general delegated computations [5].

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 20, 2023•4 citations
Abstract Lattice-based commitment schemes and their associated zero-knowledge proofs are essential building blocks for advanced lattice-based cryptographic protocols. In particular, proofs of algebraic relations among committed messages are widely used in privacy-preserving protocols such as range proofs. At CRYPTO 2020, Attema et al. proposed practical proofs for valid openings and multiplicative relations among committed values using the BDLOP commitment scheme. In their work, all commitments are generated using the same short randomness. In this paper, we consider a batch setting where commitments are generated using ℓ\ellℓ ℓ independent random vectors and present a batch valid opening proof. Our construction generalizes the approach of Baum et al. by supporting a larger challenge set and removing the requirement for invertible challenge differences. As a result, the proof size scales logarithmically with ℓ\ellℓ ℓ , rather than linearly. Furthermore, we introduce a product proof for committed messages with shared randomness across these ℓ\ellℓ ℓ commitment groups. Compared to the naive approach of applying Attema’s product proof once and repeating the opening proof ℓ−1\ell -1ℓ−1 ℓ - 1 times, our method achieves significantly better communication efficiency.
Commitment schemes are cryptographic schemes that can be applied to zero-knowledge proof construction and blockchain construction. Recently, lattice-based cryptography has been intensively investigated due to the promising potential in quantum cryptography. Accordingly, commitment schemes based on lattice assumptions have been studied for practical applications. Notably, applications often require committing an arbitrary message with low communication costs, so commitment schemes must be satisfied with fewer length restrictions and fewer extensions to the messages. Several studies have been conducted to achieve the problem, including the study published by Baum et al. in 2018. However, the scheme in question still utilizes the message domain for extraneous purposes. We design a length-extension-free commitment scheme ComMWMin which the length of the message string is large relative to the length of the commitment string, improving on the commitment scheme of Baum et al. Furthermore, we prove that the hiding and binding properties of ComMWMare based on the hardness of the decisional search knapsack problem and extended search knapsack problems, respectively. Finally, we evaluate the computation costs of generating commitment value between ours and Baum et al.’s commitment scheme.
Abstract. We design an efficient commitment scheme, and companion zero-knowledge proofs of knowledge, based on the learning with errors over rings (RLWE) problem. In particular, for rings in which almost all elements have inverses, we construct a perfectly binding commitment scheme whose hiding property relies on the RLWE assumption. Our scheme maps elements from the ring (or equivalently, n elements from Fq) to a small constant number of ring elements. We then construct Σ-protocols for proving, in a zero-knowledge manner, knowledge of the message contained in a commitment. We are able to further extend our basic protocol to allow us to prove additive and multiplicative relations among committed values. Our protocols have a communication complexity of O(Mn log q) and achieve a negligible knowledge error in one run. Here M is the constant from a rejection sampling technique that we employ, and can be set close to 1 by adjusting other parameters. Previously known Σ-protocols for LWE-related languages either relied on “smudging ” out the error (which necessitates working over large fields, resulting in poor efficiency) or only achieved a noticeable or even constant knowledge error (thus requiring many repetitions of the protocol).
We extend a commitment scheme based on the learning with errors over rings ( RLWE\mathsf{RLWE}RLWE ) problem, and present efficient companion zero-knowledge proofs of knowledge. Our scheme maps elements from the ring (or equivalently, n elements from Fq\mathbb F_qFq​ ) to a small constant number of ring elements. We then construct Σ\varSigma Σ -protocols for proving, in a zero-knowledge manner, knowledge of the message contained in a commitment. We are able to further extend our basic protocol to allow us to prove additive and multiplicative relations among committed values. Our protocols have a communication complexity of O(Mnlog⁡q)\mathcal {O}(Mn\log q)O(Mnlogq) and achieve a negligible knowledge error in one run. Here M is the constant from a rejection sampling technique that we employ, and can be set close to 1 by adjusting other parameters. Previously known Σ\varSigma Σ -protocols for LWE-related languages only achieved a noticeable or even constant knowledge error (thus requiring many repetitions of the protocol), or relied on “smudging” out the error (which necessitates working over large fields, resulting in poor efficiency).
We present a novel lattice-based zero-knowledge proof system for showing that (arbitrary-sized) committed integers satisfy additive and multiplicative relationships. The proof sizes of our schemes are between two to three orders of magnitude smaller than in the lattice proof system of Libert et al. (CRYPTO 2018) for the same relations. Because the proof sizes of our protocols grow linearly in the integer length, our proofs will eventually be longer than those produced by quantum-safe succinct proof systems for general circuits (e.g. Ligero, Aurora, etc.). But for relations between reasonably-sized integers (e.g. 512512512-bit), our proofs still result in the smallest zero-knowledge proof system based on a quantum-safe assumption. Of equal importance, the run-time of our proof system is at least an order of magnitude faster than any other quantum-safe scheme.
Abstract The lattice-based cryptographic accumulators, which enable short zero-knowledge arguments of membership, have numerous applications in post-quantum privacy-preserving protocols. However, most efficient quantum-safe zero-knowledge arguments are PCP-based systems and rely on non-falsifiable assumptions. For non-PCP-based constructions using the state-of-the-art techniques on compressing lattice-based zero-knowledge proofs, the concrete size of the resulting proof for accumulators with 2322^{32}232 members is at least 500 KB. In this paper, we propose a compact non-PCP zero-knowledge proof for the lattice-based Merkle-tree, which leads to an efficient post-quantum cryptographic accumulator. The complexity of our construction is logarithmic in l⋅nsl\cdot n_{s}l⋅ns​, where lll and nsn_{s}ns​ denote the depth of the underlying Merkle-tree and the size of a node, respectively, and the concrete size is only $143.7\ $KB when l=32l=32l=32. In particular, we provide an improved lattice-based Bulletproof with efficient knowledge extraction, which allows large challenge space but small soundness slack. Furthermore, the amortized technique can be applied to the Bulletproof without breaking the knowledge soundness due to our improved knowledge extraction. As a direct application, we present a practical lattice-based ring signature, which can achieve logarithmical signing/verifying computational complexity with the number of the ring, while the state-of-the-art constructions (CRYPTO 21) have linear computational complexity.
Lattice-based cryptography is one of the most promising candidates for designing post-quantum cryptographic algorithms that resist emerging quantum computing attacks. The recent NIST PQC standardization process is nearing its completion, with practical lattice-based algorithms for basic cryptographic functionalities (namely digital signature and public-key encryption) selected for standardization in the near future. However, practical lattice-based solutions for more advanced privacy-preserving protocols, in particular, Zero-Knowledge Proofs (ZKPs), have only emerged recently and are an active area of research. We discuss some recent developments in design and analysis of practical lattice-based post-quantum ZKPs and their applications. In particular, we review some challenges that arise in designing ZKPs in the lattice setting and some recent progress on efficient lattice-based Schnorr-like proofs for important relations, such as binary/range proofs, one-out-of-many proofs and rounding proofs [1, 2, 4]. We discuss applications and optimization of such proof systems as building blocks for practical advanced cryptographic protocols such as ring signatures and balance proofs for privacy-preserving cryptocurrency payment protocols [2, 3]. We also discuss our recent work on succinct designated-verifier ZKPs (DV-ZKSNARKS) for verifying correctness of general delegated computations [5].