×

Balancing output length and query bound in hardness preserving constructions of pseudorandom functions. (English) Zbl 1344.94035

Meier, Willi (ed.) et al., Progress in cryptology – INDOCRYPT 2014. 15th international conference on cryptology in India, New Delhi, India, December 14–17, 2014. Proceedings. Cham: Springer (ISBN 978-3-319-13038-5/pbk; 978-3-319-13039-2/ebook). Lecture Notes in Computer Science 8885, 89-103 (2014).
Summary: We revisit hardness-preserving constructions of a pseudo-random function (PRF) from any length doubling pseudo-random generator (PRG) when there is a non-trivial upper bound \(q\) on the number of queries that the adversary can make to the PRF. Very recently, A. Jain et al. [TCC 2012, Lect. Notes Comput. Sci. 7194, 369–382 (2012; Zbl 1303.94084)] gave a hardness-preserving construction of a PRF that makes only \(O(\log q)\) calls to the underlying PRG when \(q = 2^{n^\varepsilon}\) and \(\epsilon \geq \frac{1}{2}\). This dramatically improves upon the efficiency of the construction of Goldreich, Goldwasser, and Micali (FOCS 1984). However, they explicitly left open the question of whether such constructions exist when \(\epsilon < \frac{1}{2}\). In this work, we give constructions of PRFs that make only \(O(\log q)\) calls to the underlying PRG when \(q = 2^{n^\varepsilon}\), for \(0<\varepsilon <1\); our PRF outputs \(O(n^{2\varepsilon})\) bits (on every input), as opposed to the construction of Jain et al. (loc. cit.) that outputs \(n\) bits. That is, our PRF is not length preserving; however it outputs more bits than the PRF of Jain et al. (loc. cit.) when \(\varepsilon >\frac 12\). We obtain our construction through the use of information-theoretic tools such as almost \(\alpha \)-wise independent hash functions coupled with a novel proof strategy.
For the entire collection see [Zbl 1319.94007].

MSC:

94A60 Cryptography

Citations:

Zbl 1303.94084
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Goldreich, O.; Håstad, J.; Peralta, R., Simple construction of almost k-wise independent random variables, Random Struct. Algorithms, 3, 3, 289-304 (1992) · Zbl 0755.60002 · doi:10.1002/rsa.3240030308
[2] Berman, I.; Haitner, I.; Cramer, R., From non-adaptive to adaptive pseudorandom functions, Theory of Cryptography, 357-368 (2012), Heidelberg: Springer, Heidelberg · Zbl 1303.94066 · doi:10.1007/978-3-642-28914-9_20
[3] Berman, I., Haitner, I., Komargodski, I., Naor, M.: Hardness preserving reductions via cuckoo hashing. IACR Cryptology ePrint Archive 2012: 722 (2012) · Zbl 1297.94049
[4] Berman, I.; Haitner, I.; Komargodski, I.; Naor, M.; Sahai, A., Hardness preserving reductions via cuckoo hashing, Theory of Cryptography, 40-59 (2013), Heidelberg: Springer, Heidelberg · Zbl 1297.94049 · doi:10.1007/978-3-642-36594-2_3
[5] Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, November 3-5, pp. 112-117 (1982) · Zbl 0547.68046
[6] Carter, L., Wegman, M.N.: Universal classes of hash functions (extended abstract). In: Proceedings of the 9th Annual ACM Symposium on Theory of Computing, Boulder, Colorado, USA, May 4-6, pp. 106-112 (1977)
[7] Chandran, N., Garg, S.: Hardness preserving constructions of pseudorandom functions, revisited. IACR Cryptology ePrint Archive 2012: 616 (2012)
[8] Cho, C.; Lee, C-K; Ostrovsky, R.; Rabin, T., Equivalence of uniform key agreement and composition insecurity, Advances in Cryptology - CRYPTO 2010, 447-464 (2010), Heidelberg: Springer, Heidelberg · Zbl 1283.94059 · doi:10.1007/978-3-642-14623-7_24
[9] Goldreich, O.; Odlyzko, AM, Towards a theory of software protection, Advances in Cryptology - CRYPTO ’86, 426-439 (1987), Heidelberg: Springer, Heidelberg · Zbl 0627.68030 · doi:10.1007/3-540-47721-7_31
[10] Goldreich, O.; Odlyzko, AM, Two remarks concerning the goldwasser-micali-rivest signature scheme, Advances in Cryptology - CRYPTO ’86, 104-110 (1987), Heidelberg: Springer, Heidelberg · Zbl 0635.94010 · doi:10.1007/3-540-47721-7_8
[11] Goldreich, O.; Goldwasser, S.; Micali, S.; Blakely, GR; Chaum, D., On the cryptographic applications of random functions, Advances in Cryptology, 276-288 (1985), Heidelberg: Springer, Heidelberg · Zbl 1359.94599 · doi:10.1007/3-540-39568-7_22
[12] Goldreich, O.; Goldwasser, S.; Micali, S., How to construct random functions, J. ACM, 33, 4, 792-807 (1986) · Zbl 0596.65002 · doi:10.1145/6490.6503
[13] Jain, A.; Pietrzak, K.; Tentes, A.; Cramer, R., Hardness preserving constructions of pseudorandom functions, Theory of Cryptography, 369-382 (2012), Heidelberg: Springer, Heidelberg · Zbl 1303.94084 · doi:10.1007/978-3-642-28914-9_21
[14] Kurosawa, K.; Johansson, T.; Stinson, DR; Fumy, W., Almost \(k\)-wise independent sample spaces and their cryptologic applications, Advances in Cryptology - EUROCRYPT ’97, 409-421 (1997), Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-69053-0_28
[15] Levin, LA, One-way functions and pseudorandom generators, Combinatorica, 7, 4, 357-363 (1987) · Zbl 0641.68061 · doi:10.1007/BF02579323
[16] Luby, M.: Pseudorandomness and cryptographic applications. Princeton computer science notes. Princeton University Press (1996) · Zbl 0849.94017
[17] Luby, M.; Rackoff, C.; Pomerance, C., A study of password security, Advances in Cryptology - CRYPTO ’87, 392-397 (1988), Heidelberg: Springer, Heidelberg
[18] Maurer, UM; Knudsen, LR, Indistinguishability of random systems, Advances in Cryptology - EUROCRYPT 2002, 110-133 (2002), Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-46035-7_8
[19] Myers, S.; Cachin, C.; Camenisch, JL, Black-box composition does not imply adaptive security, Advances in Cryptology - EUROCRYPT 2004, 189-206 (2004), Heidelberg: Springer, Heidelberg · Zbl 1122.94390 · doi:10.1007/978-3-540-24676-3_12
[20] Naor, J.; Naor, M., Small-bias probability spaces: Efficient constructions and applications, SIAM J. Comput., 22, 4, 838-856 (1993) · Zbl 0776.60014 · doi:10.1137/0222053
[21] Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of psuedo-random functions. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, October 23-25, pp. 170-181 (1995) · Zbl 0938.68637
[22] Pietrzak, K.; Shoup, V., Composition does not imply adaptive security, Advances in Cryptology - CRYPTO 2005, 55-65 (2005), Heidelberg: Springer, Heidelberg · Zbl 1143.94352 · doi:10.1007/11535218_4
[23] Pietrzak, K.; Vaudenay, S., Composition implies adaptive security in minicrypt, Advances in Cryptology - EUROCRYPT 2006, 328-338 (2006), Heidelberg: Springer, Heidelberg · Zbl 1140.94367 · doi:10.1007/11761679_20
[24] Wegman, M.N., Carter, L.: New classes and applications of hash functions. In: 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 29-31, pp. 175-182 (1979)
[25] Yao, A.C.-C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, November 3-5, pp. 80-91 (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.