Weak pseudorandom functions in minicrypt Conference Paper

Author(s): Pietrzak, Krzysztof; Sjödin, Johan
Title: Weak pseudorandom functions in minicrypt
Title Series: LNCS
Abstract: 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).
Keywords: Adaptive security; Fixed numbers; General class; One-way functions; Pseudo-random; Pseudo-random functions; Public-key encryptions; Random functions; Range expansion
Conference Title: ICALP: Automata, Languages and Programming
Volume: 5126
Issue PART 2
Conference Dates: July 7-11, 2008
Conference Location: Reykjavik, Iceland
Publisher: Springer  
Date Published: 2008-08-06
Start Page: 423
End Page: 436
Copyright Statement: © 2008 Springer-Verlag
Sponsor: This work was partially supported by the Zurich Information Security Center.
DOI: 10.1007/978-3-540-70583-3_35
Open access: no
IST Austria Authors
Related IST Austria Work