## 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`.