ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

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).