TY - GEN
T1 - ALBATROSS: Publicly AttestabLe BATched Randomness Based On Secret Sharing
AU - Cascudo, Ignacio
AU - David, Bernardo
PY - 2020
Y1 - 2020
N2 - In this paper we present ALBATROSS, a family of multiparty randomness generation protocols with guaranteed output delivery and public verification that allows to trade off corruption tolerance for a much improved amortized computational complexity. Our basic stand alone protocol is based on publicly verifiable secret sharing (PVSS) and is secure under in the random oracle model under the decisional Diffie-Hellman (DDH) hardness assumption. We also address the important issue of constructing Universally Composable randomness beacons, showing two UC versions of Albatross: one based on simple UC NIZKs and another one based on novel efficient “designated verifier” homomorphic commitments. Interestingly this latter version can be instantiated from a global random oracle under the weaker Computational Diffie-Hellman (CDH) assumption. An execution of ALBATROSS with n parties, out of which up to t=(1/2−ϵ)⋅n are corrupt for a constant ϵ>0 , generates Θ(n2) uniformly random values, requiring in the worst case an amortized cost per party of Θ(logn) exponentiations per random value. We significantly improve on the SCRAPE protocol (Cascudo and David, ACNS 17), which required Θ(n2) exponentiations per party to generate one uniformly random value. This is mainly achieved via two techniques: first, the use of packed Shamir secret sharing for the PVSS; second, the use of linear t-resilient functions (computed via a Fast Fourier Transform-based algorithm) to improve the randomness extraction.
AB - In this paper we present ALBATROSS, a family of multiparty randomness generation protocols with guaranteed output delivery and public verification that allows to trade off corruption tolerance for a much improved amortized computational complexity. Our basic stand alone protocol is based on publicly verifiable secret sharing (PVSS) and is secure under in the random oracle model under the decisional Diffie-Hellman (DDH) hardness assumption. We also address the important issue of constructing Universally Composable randomness beacons, showing two UC versions of Albatross: one based on simple UC NIZKs and another one based on novel efficient “designated verifier” homomorphic commitments. Interestingly this latter version can be instantiated from a global random oracle under the weaker Computational Diffie-Hellman (CDH) assumption. An execution of ALBATROSS with n parties, out of which up to t=(1/2−ϵ)⋅n are corrupt for a constant ϵ>0 , generates Θ(n2) uniformly random values, requiring in the worst case an amortized cost per party of Θ(logn) exponentiations per random value. We significantly improve on the SCRAPE protocol (Cascudo and David, ACNS 17), which required Θ(n2) exponentiations per party to generate one uniformly random value. This is mainly achieved via two techniques: first, the use of packed Shamir secret sharing for the PVSS; second, the use of linear t-resilient functions (computed via a Fast Fourier Transform-based algorithm) to improve the randomness extraction.
KW - Multiparty randomness generation
KW - Publicly verifiable secret sharing (PVSS)
KW - Diffie-Hellman hardness assumption
KW - Universally Composable (UC) randomness beacons
KW - Packed Shamir secret sharing
KW - Multiparty randomness generation
KW - Publicly verifiable secret sharing (PVSS)
KW - Diffie-Hellman hardness assumption
KW - Universally Composable (UC) randomness beacons
KW - Packed Shamir secret sharing
U2 - 10.1007/978-3-030-64840-4_11
DO - 10.1007/978-3-030-64840-4_11
M3 - Article in proceedings
SN - 978-3-030-64839-8
T3 - Lecture Notes in Computer Science
SP - 311
EP - 341
BT - ASIACRYPT 2020: Advances in Cryptology – ASIACRYPT 2020
A2 - Moriai, Shiho
A2 - Wang, Huaxiong
PB - Springer
ER -