# Weak Pseudorandom Functions in Minicrypt

## Krzysztof Pietrzak and Johan Sjödin

```
```A family of functions is *weakly* pseudorandom if its members
are indistinguishable from uniformly random functions 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 {\sf
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 {\sf 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 expansion for
weak PRFs, we show that in {\sf 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 we are aware of).