The researchers Ignacio Cascudo (IMDEA Software Institute) and Bernardo David (IT University of Copenhagen) have recently published “ALBATROSS: publicly AttestabLe BATched Randomness based On Secret Sharing”.
ALBATROSS is 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.
Their 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. They also address the important issue of constructing Universally Composable randomness beacons (that can be used in more complex environments), 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 Θ(n^2) uniformly random values, requiring in the worst case an amortized cost per party of Θ(log n) exponentiations per random value. On Cascudo and David paper they significantly improve on the SCRAPE protocol, which required Θ(n^2) exponentiations per party to generate one uni- formly 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.
The main application of these protocols is in proof-of-stake blockchains, which, every certain period of time, requires to elect a “leader” among the users of the protocol, and where this selection must not be possible to be biased, and the correctness of this process needs to be able to be verified publicly.
