Paper 2009/469

Additive Combinatorics and Discrete Logarithm Based Range Protocols

Rafik Chaabouni, Helger Lipmaa, and abhi shelat

Abstract

We show how to express an arbitrary integer interval \II=[0,H] as a sumset \II=i=1Gi[0,u1]+[0,H] of smaller integer intervals for some small values , u, and H<u1, where bA={ba:aA} and A+B={a+b:aAbB}. 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 Gi 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

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. ACISP 2010
Keywords
Additive combinatoricscryptographic range proofsumsetzero knowledge
Contact author(s)
lipmaa @ research cyber ee
History
2010-04-23: last of 2 revisions
2009-09-26: received
See all versions
Short URL
https://ia.cr/2009/469
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/469,
      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},
      url = {https://eprint.iacr.org/2009/469}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.