On Wikipedia, they give the following definition of PRF:

A family of functions, $f_s: \{0,1\}^{|x|} \rightarrow \{0,1\}^{\lambda(|x|)}$, with $x\in \{0,1\}^*$ and $\lambda:\mathbb N \rightarrow \mathbb N$, is pseudorandom if the following conditions are satisfied:

  1. Given any $s$ and $x$, there always exists a polynomial-time algorithm to compute $f_{s}(x)$.
  2. (second property)

However they do not say what is the domain/range of $s$. What is this in general?


1 Answer 1


Well the variable $s$ indexes the family of pseudorandom functions, so if it is a finite family you'd have $$ \{f_s(x): 1\leq s\leq M\} $$ for some positive integer $M$ while if it is a countable family of functions, you might have $$ \{f_s(x)\}_{s \in \mathbb{N}}. $$ The functions $f$ might be considered to be randomly chosen from the set of all functions from the given domain to the given co-domain. There is no dependence on $s,$ it's just an indexing variable.

By the way the class $P$ of polynomial time algorithms is countable, i.e., infinite, so your concern does not arise. See here.

  • $\begingroup$ Thank you for your answer! My concern with the polynomial tine algorithms was not that there would be too few of them (I was not very clear). Instead, the concern is that property 1 is trivial and always holds. After all, if $f_s(x)$ is just a number or a string, then you can define the algorithm that takes no input at all and gives $f_s(x)$ as output. This is all very trivial and the definition of polynomial time does not even apply since the algorithm does not require any input. Therefore I wanted to reword that property $\endgroup$
    – Riemann
    Oct 25, 2023 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.