Biblio

Generating a secure source of publicly-verifiable randomness could be the single most fundamental technical challenge on a distributed network, especially in the blockchain context. Many current proposals face serious problems of scalability and security issues. We present a protocol which can be implemented on a blockchain that ensures unpredictable, tamper-resistant, scalable and publicly-verifiable outcomes. The main building blocks of our protocol are homomorphic encryption (HE) and verifiable random functions (VRF). The use of homomorphic encryption enables mathematical operations to be performed on encrypted data, to ensure no one knows the outcome prior to being generated. The protocol requires O(n) elliptic curve multiplications and additions as well as O(n) signature signing and verification operations, which permits great scalability. We present a comparison between recent approaches to the generation of random beacons.

In 1999, Micali, Rabin and Vadhan introduced the notion of Verifiable Random Functions (VRF)$\backslash$citeFOCS:MicRabVad99. VRFs compute for a given input x and a secret key \$sk\$ a unique function value \$y=V\_sk (x)\$, and additionally a publicly verifiable proof $π$. Each owner of the corresponding public key \$pk\$ can use the proof to non-interactivly verify that the function value was computed correctly. Furthermore, the function value provides the property of pseudorandomness. Most constructions in the past are based on q-type assumptions. Since these assumptions get stronger for a larger factor q, it is desirable to show the existence of VRFs under static or general assumptions. In this work we will show for the constructions presented in $\backslash$citePKC:DodYam05 $\backslash$citeCCS:BonMonRag10 the equivalence of breaking the VRF and solving the underlying q-type assumption.