How to construct random functions

By Oded Goldreich, Shafi Goldwasser, Silvio Micali. 1986

A constructive theory of randomness for functions, based on computational complexity, is developed, and a pseudorandom function generator is presented. This generator is a deterministic polynomial-time algorithm that transforms pairs (<italic>g</italic>, <italic>r</italic>), where <italic>g</italic> is <italic>any</italic> one-way function and <italic>r</italic> is a random <italic>k</italic>-bit string, to polynomial-time computable functions ƒ<italic><subscrpt>r</subscrpt></italic>: {1, … , 2<italic><supscrpt>k</supscrpt></italic>} → {1, … , 2<italic><supscrpt>k</supscrpt></italic>}. These ƒ<italic><subscrpt>r</subscrpt></italic>'s cannot be distinguished from <italic>random</italic> functions by any probabilistic polynomial-time algorithm that asks and receives the value of a function at arguments of its choice. The result has applications in cryptography, random constructions, and complexity theory.

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

Fairness Through Computationally-Bounded Awareness (2018, background): “The connection between learning and pseudorandom functions [23, 11] is well-established; under stronger cryptographic assumptions as in [2], the reduction implies that a running time of ⌦(|C|) is necessary for some constant ↵ > 0.”
Calibration for the (Computationally-Identifiable) Masses (2017, background): “In particular, under cryptographic assumptions [Val84, GGM84, BR17], this result implies that there is some constant t > 0, such that any algorithm that learns an α -multicalibrated predictor requires Ω( |C| t ) time.”
Relaxing Chosen-Ciphertext Security (2003, background): “In addition, let{f } 2{0,1}k be a pseudorandom function family (as in [ 14 ]).”
ANONIZE: A Large-Scale Anonymous Survey System (2014, unknown): “We assume the reader is familiar with signature schemes secure against adaptive-chosen message attacks [26], non-interactive commitment schemes [27], and pseudorandom functions [28]; see [29].”
LEAP: efficient security mechanisms for large-scale distributed sensor networks (2003, background): “• {fk} is a family of pseudo-random functions [10].”
Computational Limitations in Robust Classification and Win-Win Results (2019, background): “After d = m/8 edits to the sample, we can recover the underlying message by ignoring the first bit of the tuple and decoding the rest to get the underlying message of the form (x, c) and then use the PRF to classify.”
Verifiable random functions (1999, background): “Our VRFs are unpredictable in a very strong sense, that suitably generalizes to our context the original notion of [GGM86].”
New Proofs for NMAC and HMAC: Security without Collision Resistance (2006, methodology): “It is often used as a PRF (pseudorandom function [21]) rather than merely as a MAC.”
Order-Preserving Symmetric Encryption (2009, background): “Instead, we take the approach used in defining security e.g. of PRPs [17] or on-line PRPs [4], where one asks that oracle access to the function in question be indistinguishable from access to the corresponding “ideal” random object, e.g. a random permutation or a random on-line permutation.”
SWIFFT: A Modest Proposal for FFT Hashing (2008, background): “Suppose that our family of functions is not collision resistant; this means that there is an algorithm that, given a randomly-chosen function f from our family, is able to find a collision in f in some feasible amount of time T .”
How to Construct Quantum Random Functions (2012, methodology): “Specifically, we show that the construction from pseudorandom generators [7], the construction from pseudorandom synthesizers [11], and the direct construction based on the Learning With Errors problem [1] are all secure against quantum algorithms making quantum queries.”