TY - GEN
T1 - SCRAPE
T2 - 15th International Conference on Applied Cryptography and Network Security, ACNS 2017
AU - Cascudo, Ignacio
AU - David, Bernardo
PY - 2017
Y1 - 2017
N2 - Uniform randomness beacons whose output can be publicly attested to be unbiased are required in several cryptographic protocols. A common approach to building such beacons is having a number parties run a coin tossing protocol with guaranteed output delivery (so that adversaries cannot simply keep honest parties from obtaining randomness, consequently halting protocols that rely on it). However, current constructions face serious scalability issues due to high computational and communication overheads. We present a coin tossing protocol for an honest majority that allows for any entity to verify that an output was honestly generated by observing publicly available information (even after the execution is complete), while achieving both guaranteed output delivery and scalability. The main building block of our construction is the first Publicly Verifiable Secret Sharing scheme for threshold access structures that requires only O(n) exponentiations. Previous schemes required O(nt) exponentiations (where t is the threshold) from each of the parties involved, making them unfit for scalable distributed randomness generation, which requires t = n/2 and thus O(n2) exponentiations.
AB - Uniform randomness beacons whose output can be publicly attested to be unbiased are required in several cryptographic protocols. A common approach to building such beacons is having a number parties run a coin tossing protocol with guaranteed output delivery (so that adversaries cannot simply keep honest parties from obtaining randomness, consequently halting protocols that rely on it). However, current constructions face serious scalability issues due to high computational and communication overheads. We present a coin tossing protocol for an honest majority that allows for any entity to verify that an output was honestly generated by observing publicly available information (even after the execution is complete), while achieving both guaranteed output delivery and scalability. The main building block of our construction is the first Publicly Verifiable Secret Sharing scheme for threshold access structures that requires only O(n) exponentiations. Previous schemes required O(nt) exponentiations (where t is the threshold) from each of the parties involved, making them unfit for scalable distributed randomness generation, which requires t = n/2 and thus O(n2) exponentiations.
UR - http://www.scopus.com/inward/record.url?scp=85022329034&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-61204-1_27
DO - 10.1007/978-3-319-61204-1_27
M3 - Article in proceeding
AN - SCOPUS:85022329034
SN - 978-3-319-61203-4
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 537
EP - 556
BT - Applied Cryptography and Network Security
PB - Springer
Y2 - 10 July 2017 through 12 July 2017
ER -