Lattice-based zero-knowledge arguments for additive and multiplicative relations

Research output: Contribution to journalArticleResearchpeer-review


In this work, we propose new lattice-based protocols which are used to prove additive and multiplicative relations of committed integers. We introduce three new protocols. The first protocol proves additive relation of integers. In this framework, we introduce a new computational technique which splits the integers into chunks helping to achieve a significant improvement to the integer addition protocol proposed at CRYPTO’18 by reducing the computational costs significantly for commonly used integers of length L∈ { 2 5, 2 6, 2 7}. Our second protocol presents a new way of proving multiplicative relations of polynomials and improves the performance of the existing polynomial multiplication protocol proposed at ESORICS’15 for small integers. Using these two developed protocols as building blocks, we present our third contribution to prove multiplicative relation of integers and achieve a notable reduction in computational complexity compared to the existing integer multiplication protocol presented at CRYPTO’18.

Original languageEnglish
Pages (from-to)925–963
Number of pages39
JournalDesigns, Codes, and Cryptography
Publication statusPublished - May 2021


  • Integer addition and multiplication protocols
  • SIS assumption
  • Zero-knowledge argument

Cite this