Efficient pseudorandom functions via on-the-fly adaptation

Buch (Autor)
(Band aus einer Reihe)

Details zur Publikation

Autorinnen und Autoren: Döttling N, Schröder D
Verlag: Springer Verlag
Jahr der Veröffentlichung: 2015
Titel der Reihe: Advances in Cryptology - CRYPTO 2015
Band: 9215
Seitenbereich: 329-350
ISBN: 9783662479889
Sprache: Englisch


Pseudorandom functions (PRFs) are one of the most fundamental building blocks in cryptography with numerous applications such as message authentication codes and private key encryption. In this work, we propose a new framework to construct PRFs with the overall goal to build efficient PRFs from standard assumptions with an almost tight proof of security. The main idea of our framework is to start from a PRF for any small domain (i.e. poly-sized domain) and turn it into an l-bounded pseudorandom function, i.e., into a PRF whose outputs are pseudorandom for the first l distinct queries to F. In the second step, we apply a novel technique which we call on-the-fly adaptation that turns any bounded PRF into a fully-fledged (large domain) PRF. Both steps of our framework have a tight security reduction, meaning that any successful attacker can be turned into an efficient algorithm for the underlying hard computational problem without any significant increase in the running time or loss of success probability. Instantiating our framework with specific number theoretic assumptions, we construct a PRF based on k-LIN (and thus DDH) that is faster than all known constructions, which reduces almost tightly to the underlying problem, and which has shorter keys.Instantiating our framework with general assumptions, we construct a PRF with very flat circuits whose security tightly reduces to the security of some small domain PRF.

FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Döttling, Nico Prof. Dr.
Juniorprofessur für Kryptographische Protokolle
Schröder, Dominique Prof. Dr.
Lehrstuhl für Informatik 13 (Angewandte Kryptographie)


Döttling, N., & Schröder, D. (2015). Efficient pseudorandom functions via on-the-fly adaptation. Springer Verlag.

Döttling, Nico, and Dominique Schröder. Efficient pseudorandom functions via on-the-fly adaptation. Springer Verlag, 2015.


Zuletzt aktualisiert 2018-27-11 um 20:50