Pseudorandom Function (PRF): Difference between revisions

From Cryptology City
Jump to navigation Jump to search
No edit summary
No edit summary
 
(6 intermediate revisions by the same user not shown)
Line 6: Line 6:


PRFs were originally defined by [[ccref#ggm84|[GGM84]]] and are a basic building block for many more complex primitives such as [[Symmetric Encryption (SE)]].
PRFs were originally defined by [[ccref#ggm84|[GGM84]]] and are a basic building block for many more complex primitives such as [[Symmetric Encryption (SE)]].


== Formal Definition ==
== Formal Definition ==


=== Syntax ===
=== Syntax ===
A Pseudorandom Function (PRF) is a tuple of functions <math>(\mathsf{Gen}, F)</math>, with respect to a keyspace <math>\mathcal{K}</math>, domain <math>\mathcal{D}</math>, and range <math>\mathcal{R}</math>, such that:
A Pseudorandom Function (PRF) is a tuple of efficient functions <math>(\mathsf{Gen}, F)</math>, with respect to a keyspace <math>\mathcal{K}</math>, domain <math>\mathcal{D}</math>, and range <math>\mathcal{R}</math>, such that:
* <math>\mathsf{Gen}(1^{\lambda}) \to k</math>, takes a security parameter, and outputs a key <math>k\in \mathcal{K}</math>,
* <math>\mathsf{Gen}(1^{\lambda}) \to k</math>, is a randomized algorithm that takes a security parameter, and outputs a key <math>k\in \mathcal{K}</math>,
* <math>F_k(x) \to y</math>, takes a key <math>k\in \mathcal{K}</math> and input <math>x\in \mathcal{D}</math>, and outputs an element <math>y\in \mathcal{R}</math>.
* <math>F_k(x) \to y</math>, is a deterministic algorithm that takes a key <math>k\in \mathcal{K}</math> and input <math>x\in \mathcal{D}</math>, and outputs an element <math>y\in \mathcal{R}</math>.


Generally, we assume that <math>|\mathcal{D}|</math> is "large," in the sense that it grows exponentially with the security parameter. If instead <math>|\mathcal{D}|</math> bounded by some polynomial in the security parameter, then the primitive is a "small-domain" PRF.
Generally, we assume that <math>|\mathcal{D}|</math> is "large," in the sense that it grows exponentially with the security parameter. If instead <math>|\mathcal{D}|</math> is bounded by some polynomial in the security parameter, then the primitive is a "small-domain" PRF.


=== Security ===
=== Security ===
A PRF is ''secure'' if for all efficient <math>D</math>, there exists a negligible function <math>\nu</math>, such that
A PRF is ''secure'' if for all efficient <math>D</math>, there exists a negligible function <math>\nu</math>, such that
 
<center><math>
<math>
\big| \Pr [D^{F_k}(1^{\lambda}) = 1: k\gets \mathsf{Gen}(1^{\lambda})] -
\big| \Pr [D^{F_k}(1^{\lambda}) = 1: k\gets \mathsf{Gen}(1^{\lambda})] -
\Pr [D^{R}(1^{\lambda}) = 1 : R \gets \mathcal{F}[\mathcal{D},\mathcal{R}]] \big| \le \nu(\lambda).
\Pr [D^{R}(1^{\lambda}) = 1 : R \gets \mathcal{F}[\mathcal{D},\mathcal{R}]] \big| \le \nu(\lambda).
</math>
</math></center>


=== Weak Security ===
=== Weak Security ===
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
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
 
<center>
<math>
<math>
\big| \Pr_{x_i \gets \mathcal{D}} [D((x_i,F_k(x_i))_{i\in [s(\lambda)]}) = 1] -
\big| \Pr_{x_i \gets \mathcal{D}} [D((x_i,F_k(x_i))_{i\in [s(\lambda)]}) = 1] -
\Pr_{x_i \gets \mathcal{D}} [D((x_i,R(x_i))_{i\in [s(\lambda)]}) = 1] \big| \le \nu(\lambda).
\Pr_{x_i \gets \mathcal{D}} [D((x_i,R(x_i))_{i\in [s(\lambda)]}) = 1] \big| \le \nu(\lambda).
</math>
</math>
</center>


The difference 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 in the stronger definition.
The difference in this definition is that we sample <math>s(\lambda)</math> 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 in the stronger definition.


== Relationship to other primitives ==
== Relationship to other primitives ==
Line 41: Line 40:
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]]]


== Sufficient assumptions ==
== Sufficient assumptions ==
Line 47: Line 45:
* [[LWE]] implies [[PRF]]s
* [[LWE]] implies [[PRF]]s


 
== Variations ==
== Variations and Related Primitives ==
* [[Puncturable PRF]]
* [[Puncturable PRF]]
* [[Invertible PRF]]
* [[Invertible PRF (iPRF)]]
* [[Pseudorandom Permutation (PRP)]]
* [[Pseudorandom Permutation (PRP)]]
* [[Oblivious PRF (OPRF)]]
* [[Oblivious PRF (OPRF)]]
== Other Notes ==

Latest revision as of 02:32, 5 July 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 efficient functions , with respect to a keyspace , domain , and range , such that:

  • , is a randomized algorithm that takes a security parameter, and outputs a key ,
  • , is a deterministic algorithm that takes a key and input , and outputs an element .

Generally, we assume that is "large," in the sense that it grows exponentially with the security parameter. If instead is 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 difference in this definition is that we sample 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 in the stronger definition.

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

Other Notes