Welcome to the resource topic for 2009/469
Title:
Additive Combinatorics and Discrete Logarithm Based Range Protocols
Authors: Rafik Chaabouni, Helger Lipmaa, abhi shelat
Abstract:We show how to express an arbitrary integer interval \II = [0, H] as a sumset \II = \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 \II 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 \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.
ePrint: https://eprint.iacr.org/2009/469
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .