**Tightly-Secure Pseudorandom Functions via Work Factor Partitioning**

*Tibor Jager*

**Abstract: **We introduce a new technique for tight security proofs called work factor partitioning. Using this technique in a modified version of the framework of DÃ¶ttling and SchrÃ¶der (CRYPTO 2015), we obtain the first generic construction of tightly-secure pseudorandom functions (PRFs) from PRFs with small domain.

By instantiating the small-domain PRFs with the Naor-Reingold function (FOCS 1997) or its generalization by Lewko and Waters (ACM CCS 2009), this yields the first fully-secure PRFs whose black-box security proof loses a factor of only O(log^2 \lambda), where \lambda is the security parameter.

Interestingly, our variant of the Naor-Reingold construction can be seen as a standard Naor-Reingold PRF (whose security proof has a loss of \Theta(\lambda)), where a special encoding is applied to the input before it is processed. The tightness gain comes almost for free: the encoding is very efficiently computable and increases the length of the input only by a constant factor smaller than 2.

**Category / Keywords: **foundations / Tight security, pseudorandom functions, provable security

**Date: **received 11 Feb 2016, withdrawn 3 Oct 2016

**Contact author: **tibor jager at rub de

**Available format(s): **(-- withdrawn --)

**Version: **20161003:071807 (All versions of this report)

**Short URL: **ia.cr/2016/121

[ Cryptology ePrint archive ]