Paper 2009/469

Additive Combinatorics and Discrete Logarithm Based Range Protocols

Rafik Chaabouni, Helger Lipmaa, and abhi shelat


We show how to express an arbitrary integer interval $\II = [0, H]$ as a sumset $\II = \sum_{i=1}^\ell G_i * [0, u - 1] + [0, H']$ of smaller integer intervals for some small values $\ell$, $u$, and $H' < u - 1$, where $b * A = \{b a : a \in A\}$ and $A + B = \{a + b : a \in A \land b \in B\}$. We show how to derive such expression of $\II$ as a sumset for any value of $1 < u < H$, and in particular, how the coefficients $G_i$ can be found by using a nontrivial but efficient algorithm. This result may be interesting by itself in the context of additive combinatorics. Given the sumset-representation of $\II$, we show how to decrease both the communication complexity and the computational complexity of the recent pairing-based range proof of Camenisch, Chaabouni and shelat from ASIACRYPT 2008 by a factor of $2$. Our results are important in applications like e-voting where a voting server has to verify thousands of proofs of e-vote correctness per hour. Therefore, our new result in additive combinatorics has direct relevance in practice.

Note: This corresponds to the published version

Available format(s)
Publication info
Published elsewhere. ACISP 2010
Additive combinatoricscryptographic range proofsumsetzero knowledge
Contact author(s)
lipmaa @ research cyber ee
2010-04-23: last of 2 revisions
2009-09-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rafik Chaabouni and Helger Lipmaa and abhi shelat},
      title = {Additive Combinatorics and Discrete Logarithm Based Range Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2009/469},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.