Pseudorandom Function (PRF): Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
<noinclude> | <noinclude> | ||
[[Category:Primitives]] | [[Category:Primitives]] | ||
[[Category:Minicrypt]] | |||
A [[Pseudorandom Function (PRF)]] is a [[primitive]] | A [[Pseudorandom Function (PRF)]] is a [[primitive]] that allows someone to succinctly represent a function that is indistinguishable from a random function. A user of a PRF generates a key, which it can use to evaluate a function at many points. Any efficient adversary, who only sees these inputs and outputs of the keyed function, cannot distinguish them from a random function. | ||
PRFs were originally defined by [[ccref#ggm84|[GGM84]]] and are a basic building block for many more complex primitives such as [[Symmetric Encryption (SE)]]. | |||
Line 26: | Line 27: | ||
=== Weak Security === | === Weak Security === | ||
A PRF is ''weakly secure'' if for all efficient <math>D</math>, and all polynomials <math>s | A PRF is ''weakly secure'' if for all efficient <math>D</math>, and all polynomials <math>s</math>, there exists a negligible function <math>\nu</math>, such that | ||
<math> | <math> | ||
Line 41: | Line 42: | ||
There are also many folklore results surrounding pseudorandom functions: | There are also many folklore results surrounding pseudorandom functions: | ||
* [[PRP]]s over are [[PRF]]s, due to the switching lemma [[folklore]] | * [[PRP]]s over are [[PRF]]s, due to the switching lemma [[[folklore]]] | ||
Line 49: | Line 50: | ||
== Variations == | == Variations and Related Primitives == | ||
* [[Puncturable PRF]] | |||
* [[Invertible PRF]] | |||
* [[Pseudorandom Permutation (PRP)]] | |||
* [[Oblivious PRF (OPRF)]] |
Revision as of 02:01, 28 June 2024
A Pseudorandom Function (PRF) is a primitive that allows someone to succinctly represent a function that is indistinguishable from a random function. A user of a PRF generates a key, which it can use to evaluate a function at many points. Any efficient adversary, who only sees these inputs and outputs of the keyed function, cannot distinguish them from a random function.
PRFs were originally defined by [GGM84] and are a basic building block for many more complex primitives such as Symmetric Encryption (SE).
Formal Definition
Syntax
A Pseudorandom Function (PRF) is a tuple of functions , with respect to a keyspace , domain , and range , such that:
- , takes a security parameter, and outputs a key ,
- , takes a key and input , and outputs an element .
Generally, we assume that \$|\mathcal{D}|\$ is "large," in the sense that it grows exponentially with the security parameter. If instead bounded by some polynomial in the security parameter, then the primitive is a "small-domain" PRF.
Security
A PRF is secure if for all efficient , there exists a negligible function , such that
Weak Security
A PRF is weakly secure if for all efficient , and all polynomials , there exists a negligible function , such that
The only different in this definition is that we sample $s(\lambda)$ inputs at random instead of allowing a distinguisher to choose them. This is strictly weaker as a distinguisher could always query their oracle at random locations.
Relationship to other primitives
- PRGs imply the existence of PRFs, due to [GGM84] (this means that OWFs imply the existence of PRFs, in combination with [HILL99])
- PRFs imply the existence of PRPs, due to [LR88]
There are also many folklore results surrounding pseudorandom functions:
Sufficient assumptions