Top

Journal of Cryptology

Published in:

01-04-2015

From Non-adaptive to Adaptive Pseudorandom Functions

Authors: Itay Berman, Iftach Haitner

Published in: Journal of Cryptology | Issue 2/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Unlike the standard notion of pseudorandom functions (PRF), a non-adaptive PRF is only required to be indistinguishable from a random function in the eyes of a non-adaptive distinguisher (i.e., one that prepares its oracle calls in advance). A recent line of research has studied the possibility of a direct construction of adaptive PRFs from non-adaptive ones, where direct means that the constructed adaptive PRF uses only few (ideally, constant number of) calls to the underlying non-adaptive PRF. Unfortunately, this study has only yielded negative results (e.g., Myers in Advances in Cryptology – EUROCRYPT 2004, pp. 189–206, 2004; Pietrzak in Advances in Cryptology – CRYPTO 2005, pp. 55–65, 2005).

We give an affirmative answer to the above question, presenting a direct construction of adaptive PRFs from non-adaptive ones. The suggested construction is extremely simple, a composition of the non-adaptive PRF with an appropriate pairwise independent hash function.

previous article The Rebound Attack and Subspace Distinguishers: Application to Whirlpool

next article An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Clearly \({\mathcal{F}}\) is p-non-adaptive PRF for any \(p \in\operatorname {poly}\), but applying Theorem 1.1 with \(T\in\operatorname{poly}\), does not yield a polynomially secure adaptive PRF.

Specifically, assuming that the non-adaptive PRF is (Q,ε)-non-adaptively secure, no Q-query non-adaptive algorithm distinguishes it from random with advantage larger than ε, then the resulting PRF is \((Q,\varepsilon(1+\ln\frac{1}{\varepsilon}))\)-adaptively secure.

For our applications, see Sect. 3, we can always consider \(T'(n) = 2^{\left \lfloor \log(T(n)) \right \rfloor }\), which only causes us a factor of two loss in the resulting security.

In order to show that G of Corollary 3.9 is r-adaptive PRF, for some \(r\in \operatorname{poly}\), it is suffice to take \({\mathcal{F}}\) that is r ⁶-non-adaptive PRF. If \({\mathcal{F}}\) is assumed to be polynomially secure non-adaptive PRF, then it is also r ⁶-non-adaptive PRF, as required

That is, v is determined by the algorithm’s behavior.

In the uniform case the second parameter of v was used to represent the length of the input given to the algorithm. In contrast, in the non-uniform case, a circuit can only receive a single input length, and there is no need to give the input length as a parameter. Thus v’s domain is restricted only to \(\mathcal{S}\).

[1]

M. Bellare, A note on negligible functions. J. Cryptol., 271–284 (2002). doi:10.1007/s00145-002-0116-x

[2]

I. Berman, I. Haitner, From non-adaptive to adaptive pseudorandom functions, in Theory of Cryptography, 9th Theory of Cryptography Conference, TCC 2012 (2012), pp. 357–368

[3]

I. Berman, I. Haitner, I. Komargodski, M. Naor, Hardness preserving reductions via cuckoo hashing, in Theory of Cryptography, 10th Theory of Cryptography Conference, TCC 2013 (2013), pp. 40–59

[4]

L.J. Carter, M.N. Wegman, Universal classes of hash functions. J. Comput. Syst. Sci., 143–154 (1979). doi:10.1145/800105.803400

[5]

C. Cho, C.-K. Lee, R. Ostrovsky, Equivalence of uniform key agreement and composition insecurity, in Advances in Cryptology – CRYPTO 2010 (2010), pp. 447–464 CrossRef

[6]

I. Damgård, J.B. Nielsen, Expanding pseudorandom functions; or: from known-plaintext security to chosen-plaintext security, in Advances in Cryptology – CRYPTO 2002 (2002), pp. 449–464 CrossRef

[7]

Y. Dodis, E. Kiltz, K. Pietrzak, D. Wichs, Message authentication, revisited, in Advances in Cryptology – EUROCRYPT 2012 (2012), pp. 355–374 CrossRef

[8]

O. Goldreich, Foundations of Cryptography: Basic Tools (Cambridge University Press, Cambridge, 2001) CrossRef

[9]

O. Goldreich, Foundations of Cryptography – VOLUME 2: Basic Applications (Cambridge University Press, Cambridge, 2004) CrossRef

[10]

O. Goldreich, S. Goldwasser, S. Micali, On the cryptographic applications of random functions, in Advances in Cryptology – CRYPTO ’84 (1984), pp. 276–288

[11]

O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions. J. ACM, 792–807 (1986). doi:10.1445/6490.6503

[12]

J. Håstad, R. Impagliazzo, L.A. Levin, M. Luby, A pseudorandom generator from any one-way function. SIAM J. Comput., 1364–1396 (1999). doi:10.1137/s0097539793244708

[13]

M. Luby, Pseudorandomness and Cryptographic Applications. Princeton Computer Science Notes. (Princeton University Press, Princeton, 1996). ISBN 978-0-691-02546-9 MATH

[14]

V. Lyubashevsky, D. Masny, Man-in-the-middle secure authentication schemes from LPN and weak PRFS. IACR Cryptol. ePrint Arch. 2013, 92 (2013)

[15]

U.M. Maurer, K. Pietrzak, Composition of random systems: when two weak make one strong, in Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004 (2004), pp. 410–427

[16]

U.M. Maurer, J. Sjödin, A fast and key-efficient reduction of chosen-ciphertext to known-plaintext security, in Advances in Cryptology – EUROCRYPT 2007 (2007), pp. 498–516 CrossRef

[17]

U.M. Maurer, S. Tessaro, Basing PRFS on constant-query weak PRFS: minimizing assumptions for efficient symmetric cryptography, in Advances in Cryptology – ASIACRYPT 2008 (2008), pp. 161–178 CrossRef

[18]

S. Myers, Black-box composition does not imply adaptive security, in Advances in Cryptology – EUROCRYPT 2004 (2004), pp. 189–206 CrossRef

[19]

M. Naor, O. Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions. J. Comput. Syst. Sci., 336–375 (1999). doi:10.1006/jcss.1998.1618

[20]

K. Pietrzak, Composition does not imply adaptive security, in Advances in Cryptology – CRYPTO 2005 (2005), pp. 55–65 CrossRef

[21]

K. Pietrzak, Composition implies adaptive security in minicrypt, in Advances in Cryptology – EUROCRYPT 2006 (2006), pp. 328–338 CrossRef

Title: From Non-adaptive to Adaptive Pseudorandom Functions
Authors: Itay Berman
Iftach Haitner
Publication date: 01-04-2015
Publisher: Springer US
Published in: Journal of Cryptology / Issue 2/2015
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-013-9169-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2015

Efficient Recursive Diffusion Layers for Block Ciphers and Hash Functions

Computing on Authenticated Data

New Attacks on IDEA with at Least 6 Rounds

The Rebound Attack and Subspace Distinguishers: Application to Whirlpool

An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

Premium Partner