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
ℓ ℓ 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
ℓ ℓ , rather than linearly. Furthermore, we introduce a product proof for committed messages with shared randomness across these
ℓ ℓ commitment groups. Compared to the naive approach of applying Attema’s product proof once and repeating the opening proof
ℓ−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.