<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\ell\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\ell\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>, rather than linearly. Furthermore, we introduce a product proof for committed messages with shared randomness across these <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\ell\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> commitment groups. Compared to the naive approach of applying Attema’s product proof once and repeating the opening proof <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\ell -1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> times, our method achieves significantly better communication efficiency.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Proving multiplicative relations for lattice commitments in batch

  • Mengfan Wang,
  • Guifang Huang,
  • Dong Fang,
  • Lei Hu

摘要

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.