Chaabouni, Rafik
Lipmaa, Helger
Shelat, Abhi
Additive Combinatorics and Discrete Logarithm Based Range Protocols
Information Security and Privacy Information Security and Privacy, Proceedings of the 15th Australasian Conference, ACISP 2010
978-3-642-14080-8
10.1007/978-3-642-14081-5_21
6168
336-351
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 \wedge 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.
Additive combinatorics;
Cryptographic range proof;
Sumset;
Zero knowledge;
Springer
Berlin Heidelberg
2010
http://www.springerlink.com/content/w880647l0k3x5732/;
http://infoscience.epfl.ch/record/150533/files/ChaabouniLS10.pdf;
http://infoscience.epfl.ch/record/150533/files/cls10_acisp_static.pdf;