Verifiable random functions

By Silvio Micali, M. Rabin, Salil P. Vadhan. 1999

We efficiently combine unpredictability and verifiability by extending the Goldreich-Goldwasser-Micali (1986) construction of pseudorandom functions f/sub s/ from a secret seed s, so that knowledge of s not only enables one to evaluate f/sub s/ at any point x, but also to provide an NP-proof that the value f/sub s/(x) is indeed correct without compromising the unpredictability of f/sub s/ at any other point for which no such a proof was provided.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Biscotti: A Ledger for Private and Secure Peer-to-Peer Machine Learning (2018, methodology): “Each verifier receives the following from each peer i: • The masked SGD update: (∆wi +∑k ζk) • Commitment to the SGD update: COMM(∆wi) • The set of k noise commitments: {COMM(ζ1),COMM(ζ2), ...,COMM(ζk))} • A VRF proof confirming the identity of the k noise peers When a verifier receives a masked upd”
CONIKS: Bringing Key Transparency to End Users (2015, methodology): “We can implement a VRF by applying a hash function (modeled as a random oracle) to the result of any deterministic, existentially unforgeable signature scheme [48].”
Solutions to Scalability of Blockchain: A Survey (2020, methodology): “By combining with Verifiable Random Functions [74], users are chosen to become a committee member to participate in the BA and reach consensus on the next set of transactions.”
Applications of Multilinear Forms to Cryptography (2002, methodology): “Unique signatures are used to construct Verifiable Pseudo Random Functions, which are a useful tool in cryptographic protocol design [20].”
Scalable Bias-Resistant Distributed Randomness (2017, methodology): “To address this issue, we can use a lottery mechanism that depends on verifiable random functions (VRFs) [43], which ensures that each participant obtains an unpredictable “fairshare” chance of getting to be the leader in each round.”
A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks (2018, methodology): “the verifiable random function defined in [67]), we can abstract a PoX process by the three stages described in Table 1.”
Vector Commitments and Their Applications (2013, methodology): “In [21] is given a definition of Updatable Zero Knowledge (Elementary) Databases together with a construction based on mercurial commitments and Verifiable Random Functions [25] in the random oracle model.”
A Survey of Distributed Consensus Protocols for Blockchain Networks (2019, methodology): “Because of its reduced synchrony requirement and the privacy-preserving nature of the VRF scheme, Ouroboros Praos does not limit the size of consensus participants and allows for a flexible committee.”
Pseudorandom Functions: Three Decades Later (2017, background): “The construction of authentication schemes from PRFs extends naturally to provide digital signatures from verifiable PRFs [23, 100].”
Universally composable signature, certification, and authentication (2004, background): “The second is reminiscent of verifiable random functions [mrv99]; however, whereas verifiable random functions do not guarantee that the signature value “appears random” to the signer, the above alternative formulation does.”
Functional Signatures and Pseudorandom Functions (2014, background): “A verifiable PRF, introduced by Micali, Rabin and Vadhan in [25] has the property that, in addition to the secret seed s of the PRF, there is a corresponding public key pks and a way to generate a proof πx given the secret seed, such that given pks, x, y and πx, one can check that y is indeed the co”
Algorand: Scaling Byzantine Agreements for Cryptocurrencies (2017, methodology): “A key technique that makes BA⋆ suitable for Algorand is the use of verifiable random functions (VRFs) [39] to randomly select users in a private and non-interactive way.”
Towards Scaling Blockchain Systems via Sharding (2018, methodology): “fically, we implement a trusted randomness beacon inside the TEE to generate unbiased random values in a distributed setting, which achieves significant speed-up over existing cryptographic protocols [38, 44]. Furthermore, we exploit the increased fault tolerance of our TEE-assisted BFT consensus pr”
Biscotti: A Blockchain System for Private and Secure Federated Learning (2021, methodology): “To prevent such attacks, Biscotti requires that every peer pre-commits the noise vector z t for every future iteration t 2 ½ 1 ::T (cid:5) in the genesis block, and that each iteration uses a private VRF to select a group of noising peers based on the victim C ’s secret key.”
Enabling Security in Cloud Storage SLAs with CloudProof (2011, background): “The attestations are key components that allow the clients to prove cloud misbehavior and the cloud to defend himself against false accusations.”
Constant-Size Dynamic k-TAA (2006, methodology): “Our constant-size dynamic k-TAA make use of verifiable random function (VRF), introduced in [14].”
OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding (2018, methodology): “Sortition is implemented using a verifiable random function (VRF) [35] that takes an input x and returns a random hash (l-bit long string) and a proof π based on ski.”
RapidChain: Scaling Blockchain via Full Sharding (2018, methodology): “Algorand [32] proposes a committee-based consensus protocol called BA? that uses a verifiable random function (VRF) [51] to randomly select committee members, weighted by their account balances (i.”