2
$\begingroup$

I am wondering about the setup for testing if a function family is pseudorandom. We step into a room, and query the black box with $x$, which yields $f(x)$, etc... We don't know if $f$ is a random function, or if it comes from some preset function family $F$. In the latter case, what assumptions are made about the functions in $F$? Is it enough for each $f$ in $F$ to be listed as a table in the black box, so that $f: \{0,1\}^n \to \{0,1\}^n$ is listed as a table with $2^n$ entries? What if $f$ is described by some function of a polynomial with coefficients that are exponential in $n$? What are the restrictions on the functions in the function family $F$, if any?

$\endgroup$
2
$\begingroup$

For the definition of pseudorandomness, the family $F$ of functions can be any set of functions at all. But typically we take it to be a set where each function can be described by a rather short key/seed, and where one can efficiently compute the function output given the input (and the key). This is because we want the family $F$ to represent functions that we can randomly choose from and use in real life.

For example, $F$ could be the set of functions AES$_k$, taken over all 128-bit strings $k$ (where AES$_k$ denotes the AES block cipher with key $k$). Notice that there are "only" $2^{128}$ functions in this family, which is much less than the number of functions mapping 128 bits to 128 bits (which is $(2^{128})^{2^{128}}$).

$\endgroup$
-1
$\begingroup$

Pseudorandom functions just have to produce 'random' values, there are no special restrictions on the functions.

There are tests to measure the quality of random functions. These tests will try to detect if the outputs of a function are somehow correlated or biased.

A well-known test battery are the Diehard Tests from George Marsaglia. Or you have more recent tests here.

PS: Often random functions will just generate a random sequence based on an initial seed value; you don't have to pass a parameter $x$ each time you call the function. While such random functions do exist, the box in your description somehow reminds me of a hash function (or a random oracle).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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