# Weak Pseudorandom Functions in Minicrypt

## Krzysztof Pietrzak and Johan Sjödin

```
```A family of functions is weakly pseudorandom if a random
member of the family is indistinguishable from a uniform random function
when queried on random inputs. We point out a subtle ambiguity
in the definition of weak PRFs: there are natural weak PRFs whose
security breaks down if the randomness used to sample the inputs is
revealed. To capture this ambiguity we distinguish between public-coin
and secret-coin weak PRFs.
We show that the existence of a secret-coin weak PRF which is not also
a public-coin weak PRF implies the existence of two pass key-agreement
(i.e. public-key encryption). So in Minicrypt, i.e. under the assumption
that one-way functions exist but public-key cryptography does not, the
notion of public- and secret-coin weak PRFs coincide.
Previous to this paper all positive cryptographic statements known
to hold exclusively in Minicrypt concerned the adaptive security of constructions
using non-adaptively secure components.Weak PRFs give rise
to a new set of statements having this property. As another example we
consider the problem of range extension for weak PRFs. We show that in
Minicrypt one can beat the best possible range expansion factor (using a
fixed number of distinct keys) for a very general class of constructions (in
particular, this class contains all constructions that are known today).