2008 | OriginalPaper | Buchkapitel
Weak Pseudorandom Functions in Minicrypt
verfasst von : Krzysztof Pietrzak, Johan Sjödin
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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).