150533
20181126110018.0
978-3-642-14080-8
10.1007/978-3-642-14081-5_21
doi
000284032000021
ISI
CONF
Additive Combinatorics and Discrete Logarithm Based Range Protocols
Berlin Heidelberg
2010
Springer
2010
Conference Papers
LNCS
6168
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
Chaabouni, Rafik
152151
243332
Lipmaa, Helger
Shelat, Abhi
15th Australasian Conference, ACISP 2010
Sydney, Australia
July 5-7, 2010
336-351
Information Security and Privacy Information Security and Privacy, Proceedings of the 15th Australasian Conference, ACISP 2010
6168
URL
http://www.springerlink.com/content/w880647l0k3x5732/
603410
n/a
http://infoscience.epfl.ch/record/150533/files/ChaabouniLS10.pdf
323469
n/a
http://infoscience.epfl.ch/record/150533/files/cls10_acisp_static.pdf
LASEC
252183
U10433
oai:infoscience.tind.io:150533
IC
conf
GLOBAL_SET
152151
152151
186617
152151
152151
EPFL-CONF-150533
EPFL
PUBLISHED
REVIEWED
CONF