Additive Combinatorics and Discrete Logarithm Based Range Protocols

We show how to express an arbitrary integer interval

$\mathcal{I} = [0, H]$

as a sumset

$\mathcal{I} = \sum_{i=1}^\ell G_i * [0, u - 1] + [0, H']$

of smaller integer intervals for some small values ℓ,

u

, and

H

′ < 

u

 − 1, where

b

*

A

 = {

b

a

:

a

 ∈ 

A

} and

$A + B = \{a + b : a \in A \land b \in B\}$

. We show how to derive such expression of

$\mathcal{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

$\mathcal{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.