Abstract
A common method for increasing the usability and uplifting the security of pseudorandom function families (PRFs) is to “hash” the inputs into a smaller domain before applying the PRF. This approach, known as “Levin’s trick”, is used to achieve “PRF domain extension” (using a short,e.g,fixed, input length PRF to get a variable-length PRF), and more recently to transform non-adaptive PRFs to adaptive ones. Such reductions, however, are vulnerable to a “birthday attack”: after \(\sqrt{|\mathcal{U}}\) queries to the resulting PRF, where \(\mathcal{U}\) being the hash function range, a collision (i.e., two distinct inputs have the same hash value) happens with high probability. As a consequence, the resulting PRF is insecure against an attacker making this number of queries.
In this work we show how to go beyond the birthday attack barrier, by replacing the above simple hashing approach with a variant of cuckoo hashing — a hashing paradigm typically used for resolving hash collisions in a table, by using two hash functions and two tables, and cleverly assigning each element into one of the two tables. We use this approach to obtain: (i) A domain extension method that requires just two calls to the original PRF, can withstand as many queries as the original domain size and has a distinguishing probability that is exponentially small in the non cryptographic work. (ii) A security-preserving reduction from non-adaptive to adaptive PRFs.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aiello, W., Venkatesan, R.: Foiling Birthday Attacks in Length-Doubling Transformations - Benes: a non-reversible alternative to Feistel. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 307–320. Springer, Heidelberg (1996)
Arbitman, Y., Naor, M., Segev, G.: Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. In: Proceedings of the 51th Annual Symposium on Foundations of Computer Science (FOCS), pp. 787–796 (2010)
Aumüller, M., Dietzfelbinger, M., Woelfel, P.: Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 108–120. Springer, Heidelberg (2012)
Bellare, M., Goldwasser, S.: New Paradigms for Digital Signatures and Message Authentication Based on Non-interactive Zero Knowledge Proofs. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 194–211. Springer, Heidelberg (1990)
Bellare, M., Goldreich, O., Krawczyk, H.: Stateless Evaluation of Pseudorandom Functions: Security beyond the Birthday Barrier. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 270–287. Springer, Heidelberg (1999)
Berman, I., Haitner, I.: From Non-adaptive to Adaptive Pseudorandom Functions. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 357–368. Springer, Heidelberg (2012)
Blum, M., Evans, W.S., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. Algorithmica 12(2/3), 225–244 (1994)
Carter, L.J., Wegman, M.N.: Universal classes of hash functions. Journal of Computer and System Sciences, 143–154 (1979)
Chandran, N., Garg, S.: Hardness preserving constructions of pseudorandom functions, revisited. IACR Cryptology ePrint Archive 2012:616 (2012)
Chor, B., Fiat, A., Naor, M., Pinkas, B.: Tracing traitors. IEEE Transactions on Information Theory 46(3), 893–910 (2000)
Dietzfelbinger, M., Woelfel, P.: Almost random graphs with simple hash functions. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 629–638 (2003)
Goldreich, O.: Towards a Theory of Software Protection. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 426–439. Springer, Heidelberg (1987)
Goldreich, O., Goldwasser, S., Micali, S.: On the Cryptographic Applications of Random Functions. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 276–288. Springer, Heidelberg (1985)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of the ACM, 792–807 (1986)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM Journal on Computing, 1364–1396 (1999)
Jain, A., Pietrzak, K., Tentes, A.: Hardness Preserving Constructions of Pseudorandom Functions. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 369–382. Springer, Heidelberg (2012)
Jetchev, D., Özen, O., Stam, M.: Understanding Adaptivity: Random Systems Revisited. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 313–330. Springer, Heidelberg (2012)
Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica 7(4), 357–363 (1987)
Luby, M.: Pseudorandomness and cryptographic applications. Princeton computer science notes. Princeton University Press (1996)
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing 17(2), 373–386 (1988)
Maurer, U.M.: Indistinguishability of Random Systems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 110–132. Springer, Heidelberg (2002)
Maurer, U.M., Pietrzak, K.: Composition of Random Systems: When Two Weak Make One Strong. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 410–427. Springer, Heidelberg (2004)
Myers, S.: Black-Box Composition Does Not Imply Adaptive Security. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 189–206. Springer, Heidelberg (2004)
Nandi, M.: A Unified Method for Improving PRF Bounds for a Class of Blockcipher Based MACs. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 212–229. Springer, Heidelberg (2010)
Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of psuedo-random functions. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pp. 170–181 (1995)
Ostrovsky, R.: An Efficient Software Protection Scheme. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 610–611. Springer, Heidelberg (1990)
Pagh, A., Pagh, R.: Uniform hashing in constant time and optimal space. SIAM Journal on Computing 38(1), 85–96 (2008)
Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122–144 (2004)
Patarin, J.: Security of Random Feistel Schemes with 5 or More Rounds. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 106–122. Springer, Heidelberg (2004)
Patarin, J.: A Proof of Security in O(2n) for the Benes Scheme. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 209–220. Springer, Heidelberg (2008)
Patarin, J.: Security of balanced and unbalanced feistel schemes with linear non equalities. IACR Cryptology ePrint Archive, 2010:293 (2010)
Pietrzak, K.: Composition Does Not Imply Adaptive Security. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 55–65. Springer, Heidelberg (2005)
Pietrzak, K.: Composition Implies Adaptive Security in Minicrypt. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 328–338. Springer, Heidelberg (2006)
Siegel, A.: On universal classes of extremely random constant-time hash functions. SIAM Journal on Computing 33(3), 505–543 (2004)
Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22(3), 265–279 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 International Association for Cryptologic Research
About this paper
Cite this paper
Berman, I., Haitner, I., Komargodski, I., Naor, M. (2013). Hardness Preserving Reductions via Cuckoo Hashing. In: Sahai, A. (eds) Theory of Cryptography. TCC 2013. Lecture Notes in Computer Science, vol 7785. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36594-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-36594-2_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36593-5
Online ISBN: 978-3-642-36594-2
eBook Packages: Computer ScienceComputer Science (R0)