摘要

We show how to express an arbitrary integer interval I = [0, H] as a sumset I = Sigma(l)(i=1) G(i) * [0, u - 1] + [0, H'] of smaller integer intervals for some small values l, u, and H' < u - 1, where b * A = {ba: a is an element of A} and A + B = {a + b : a is an element of A boolean AND b is an element of 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 ill 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.

  • 出版日期2010