Pseudorandom Function (PRF): Difference between revisions

From Cryptology City
Jump to navigation Jump to search
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]] originally defined in [cite].
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.


TOOD: information definition
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(\lambda)</math>, there exists a negligible function <math>\nu</math>, such that
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

There are also many folklore results surrounding pseudorandom functions:

  • PRPs over are PRFs, due to the switching lemma [[[folklore]]]


Sufficient assumptions


Variations and Related Primitives