## Additive Combinatorics and Discrete Logarithm Based Range Protocols

Rafik Chaabouni, Helger Lipmaa and abhi shelat. Additive Combinatorics and Discrete Logarithm Based Range Protocols. In Ron Steinfeld and Philip Hawkes, editors, ACISP 2010, volume 6168 of Lecture Notes in Computer Science, pages 336--351, Sydney, Australia, July 5--7, 2010. Springer, Heidelberg.

File: [.pdf (589 KB)] pdf recommended.

Abstract:

We show how to express an arbitrary integer interval $I = [0, H]$ as a sumset $I = \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 $I$ 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 $I$, 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..

Keywords: Additive combinatorics, cryptographic range proof, sumset, zero knowledge.

Authors:

Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa>gmail.com.