1
$\begingroup$

Consider a function $f: \{0,1\}^n \to \{0,1\}^{cn}$, where $c>1$.

A random $f$ with high probability generates optimal covering of $\{0,1\}^{cn}$, i. e.:

$\forall x \in \{0,1\}^{cn}$ $\exists y \in Im(f): |x - y| < r + O(\log n)$,

where || - Hamming norm and $r$ is number such that volume of a full-sphere with radius $r$ is equal to $|\{0,1\}^{cn}| : |\{0,1\}^n| = 2^{cn} : 2^n = 2^{(c-1)n}$.

We don't know any $f$ such that can be calculated in polynomial of $n$ time and generates optimal covering.

But what is about Cryptographically secure pseudorandom generator(PG, https://en.wikipedia.org/wiki/Pseudorandom_generator) $f$?

In this case $f$ can be calculated in polynomial of $n$ time. Unfortunately from the definition of PG it is not follows that $f$ generates optimal covering (as in the case of Nisan-Wigderson generator). But anyway if $f$ doesn't generate optimal covering it may be used for some attack on a conjecturally PG function (i. e. for proving that some conjecturally PG are not PG really), I think.

Are there a results about functions that might be PG, but don't generate optimal covering?

$\endgroup$

1 Answer 1

1
$\begingroup$

The difficulty here is the exact definition of PRF. A PRF is a function $f(k,x)$ which is computationally indistinguishable from a random function of $x$ when we pick $k$ randomly. This does not mean $f(k,x)$ for a fixed $k$ is a random function.

The other obstacle is that we do not know any PRFs, only conjectured ones. There are very few unconditional results in cryptography.

$\endgroup$
2

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.