Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptology
Published in: Journal of Cryptology 2/2019

07-05-2018

Hardness-Preserving Reductions via Cuckoo Hashing

Authors: Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor

Published in: Journal of Cryptology | Issue 2/2019

Log in

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

search-config
loading …

Abstract

The focus of this work is hardness-preserving transformations of somewhat limited pseudorandom functions families (PRFs) into ones with more versatile characteristics. Consider the problem of domain extension of pseudorandom functions: given a PRF that takes as input elements of some domain \(\mathcal {U}\), we would like to come up with a PRF over a larger domain. Can we do it with little work and without significantly impacting the security of the system? One approach is to first hash the larger domain into the smaller one and then apply the original PRF. Such a reduction, however, is vulnerable to a “birthday attack”: after \(\sqrt{\left| \mathcal {U}\right| }\) queries to the resulting PRF, a collision (i.e., two distinct inputs having the same hash value) is very likely to occur. 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 aforementioned birthday attack barrier by replacing the above simple hashing approach with a variant of cuckoo hashing, a hashing paradigm that resolves collisions in a table by using two hash functions and two tables, cleverly assigning each element to 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 amount of non-cryptographic work; and (ii) a security-preserving reduction from non-adaptive to adaptive PRFs.
previous article Automated Analysis of Cryptographic Assumptions in Generic Group Models
next article Non-black-box Simulation in the Fully Concurrent Setting, Revisited

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
Appendix
Available only for authorised users
Footnotes
1
In this context, a dictionary is a data structure used for maintaining a set of elements while supporting membership queries.
 
2
The \(\mathcal {ADW}\)’s function family is in fact more complicated than the above simplified description. See Sect. 6 for the formal definition.
 
3
Note that in some cases an adaptive adversary is a more powerful distinguisher than a non-adaptive one. For example, when trying to distinguish between a truly random function and a random involution (permutations where the cycle length is at most 2), there exists an adaptive distinguisher that will succeed with very high probability by asking two queries, while any non-adaptive distinguisher will fail with very high probability (see [28, 42]).
 
4
Pagh and Pagh [44] did notice this connection, and in particular mentioned the connection of their work to that of Bellare et al. [7].
 
5
This is by no means an exhaustive list of all domain extension constructions that achieve beyond-birthday security.
 
6
Of course, one can use these constructions to extend the domain to any \({\text {poly}}(n)\) length by a recursive construction. This, however, will increase the number of calls to the underlying PRF by a polynomial factor.
 
7
Berman and Haitner [8] do give a single transformation for all poly-time adversaries with the additional cost of slightly increasing the number of calls to the underlying non-adaptive PRF. Their transformation can be carried to our setting and be applied with the \(\mathcal {PP}\) function family. However, our construction is superior to [8]’s only by reducing the security loss in a polynomial factor, a factor that is meaningless when considering all poly-time adversaries. Thus, we avoid stating our result in this all poly-time adversaries setting and refer to [8] for such a result.
 
8
Formally, a function family \(\mathcal{{H}}=\{h:\mathcal {D}\mapsto \mathcal {R}\}\) is \((\varepsilon ,k)\)-wise independent if for any \(x_1,\dots ,x_k\in \mathcal {D}\) and for any \(y_1,\dots ,y_k\in \mathcal {R}\) it holds that \(\left| {\mathrm {Pr}}_{h\leftarrow \mathcal{{H}}}[h(x_1)=y_1\wedge \dots \wedge h(x_k)=y_k]-\left| \mathcal {R}\right| ^{-k}\right| \le \varepsilon \). We call a family of functions an almost k-wise independent family, if it is \((\varepsilon ,k)\)-wise independent for some small \(\varepsilon >0\).
 
9
See Footnote 3 and references therein.
 
10
[10] only states and proves the adaptive case, but the very same argument also yields the non-adaptive case.
 
11
That is, \({\mathsf {D}}(1^n)\) runs in time \(t(n) + s\cdot q(n) \cdot e_\mathcal{F}(n)\). Moreover, we implicitly assume that the evaluation time of \(\mathcal{F}\) is greater than the time needed to sample \(\ell (n)\) random bits.
 
12
Recall that for a set \(\mathcal {S}\) and an integer t, \(\mathcal {S}^{\le t}\) denotes the set \(\{\overline{s}\in \mathcal {S}^*:\left| \overline{s}\right| \le t \ \ \wedge \ \ \overline{s}[i] \ne \overline{s}[j] \ \ \forall i \ne j \in [\left| \overline{s}\right| ]\}\).
 
13
Lemma 3.2 can be derived as a special case of a result given in [27, Theorem 12] (closing a gap in the proof appearing in [33]). Yet, for the sake of completeness, we include an independent proof of this lemma here.
 
14
The function family we consider above (i.e., \(\mathcal {PP}\)) is slightly different than the one given in [44]. Their construction maps element \(x\in \mathcal {D}\) to \(F_1[h_1(x)]\oplus F_2[h_2(x)] \oplus g(x)\), where \(F_1\) and \(F_2\) are uniformly chosen vectors from \(\mathcal {R}^t\), \(h_1,h_2 :\mathcal {D}\mapsto [t]\) are uniformly chosen from a function family \(\mathcal{{H}}\) and \(g:\mathcal {D}\mapsto \mathcal {R}\) is chosen uniformly from a function family \(\mathcal {G}\). Yet, the correctness of Theorem 3.4 follows in a straightforward manner from [44] original proof (specifically from Lemmas 3.3 and 3.4).
 
15
Note that \(a_{h_1, \overline{g},\overline{m}^1},a_{h_2, \overline{g},\overline{m}^2}:\mathcal {D}\mapsto \mathcal {S}\) uses \(\oplus _\mathcal {S}\) and \(a_{\ell , \overline{g},\overline{y}}:\mathcal {D}\mapsto \mathcal {R}\) uses \(\oplus _\mathcal {R}\).
 
16
The actual setting in [4] is more general. Specifically, an additional parameter \(\varepsilon >0\) is used to set the size of \(\mathcal {S}\) as \((1+\varepsilon )t\). For simplicity of presentation, comparison with the statement of Theorem 3.4, and since we use this theorem only when m is an integer, we set \(\varepsilon =3\).
 
17
The independence affects the amount of random bits and evaluation time needed for these families.
 
18
Another criterion of comparison is the sampling time. In our settings it is analogous to the evaluation time, so we omit it.
 
19
Recall that for a set \(\mathcal {S}\) and an integer t, \(\mathcal {S}^{\le t}\) denotes the set \(\{\overline{s}\in \mathcal {S}^*:\left| \overline{s}\right| \le t \ \ \wedge \ \ \overline{s}[i] \ne \overline{s}[j] \ \ \forall i \ne j \in [\left| \overline{s}\right| ]\}\).
 
20
\(\mathcal {GGM} _{m(n)\rightarrow \ell (n)}^G\) is a variant of the standard \(\mathcal {GGM} \) function family, that on input of length m(n) uses seed of length \(\ell (n)\) for the underlying generator, rather than seed of length m(n). Formally, \(\mathcal {GGM} _{m\rightarrow \ell }^G\) is the function family ensemble \(\{\mathcal {GGM} ^G_{m(n)\rightarrow \ell (n)}\}_{n\in {\mathbb {N}}}\), where \(\mathcal {GGM} ^G_{m(n)\rightarrow \ell (n)} = \{f_r\}_{r\in \{0,1\}^{\ell (n)}}\), and for \(r\in \{0,1\}^{\ell (n)}\), the oracle-aided function \(f_r:\{0,1\}^{m(n)} \mapsto \{0,1\}^{\ell (n)}\) is defined as follows: given oracle access to a length-doubling function G and input \(x\in \{0,1\}^{m(n)}\), \(f_r^G(x) = r_x\), where \(r_x\) is recursively defined by \(r_\varepsilon =r\), and, for a string w, \(r_{w||0} || r_{w||1} = G(r_w)\). The original \(\mathcal {GGM} \) construction was length-preserving, i.e., \(m(n)=\ell (n)=n\).
 
Literature
1.
W. Aiello, R. Venkatesan, Foiling birthday attacks in length-doubling transformations - benes: A non-reversible alternative to feistel, in Advances in Cryptology—EUROCRYPT ’96, pp. 307–320 (1996)
2.
Y. Arbitman, M. Naor, G. Segev, 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)
3.
M. Aumüller, M. Dietzfelbinger, P. Woelfel, Explicit and efficient hash families suffice for cuckoo hashing with a stash, in L. Epstein and P. Ferragina, editors, ESA, volume 7501 of Lecture Notes in Computer Science (Springer, 2012), pp. 108–120
4.
M. Aumüller, M. Dietzfelbinger, P. Woelfel, Explicit and efficient hash families suffice for cuckoo hashing with a stash. Algorithmica, 70(3), 428–456, (2014)MathSciNetCrossRefMATH
5.
M. Bellare, S. Goldwasser, New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs, in Advances in Cryptology—CRYPTO ’89, pp. 194–211 (1989)
6.
M. Bellare, R. Canetti, H. Krawczyk, Pseudorandom functions revisited: The cascade construction and its concrete security, in FOCS, pp. 514–523 (1996)
7.
M. Bellare, O. Goldreich, H. Krawczyk, Stateless evaluation of pseudorandom functions: Security beyond the birthday barrier, in Advances in Cryptology—CRYPTO ’99, pp. 270–287 (1999)
8.
9.
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, pp. 40–59 (2013)
10.
O. Billet, J. Etrog, H. Gilbert, Lightweight privacy preserving authentication for rfid using a stream cipher, in 18th International Symposium on the Foundations of Software Engineering (FSE), pp. 55–74 (2010)
11.
M. Blum, W.S. Evans, P. Gemmell, S. Kannan, M. Naor, Checking the correctness of memories. Algorithmica, 12(2/3), 225–244 (1994)MathSciNetCrossRefMATH
12.
L.J. Carter, M.N. Wegman, Universal classes of hash functions. J. Comput. Syst. Sci., 143–154 (1979)
13.
N. Chandran, S. Garg, Balancing output length and query bound in hardness preserving constructions of pseudorandom functions, in Progress in Cryptology—INDOCRYPT 2014, pp. 89–103 (2014)
14.
B. Chor, A. Fiat, M. Naor, B. Pinkas, Tracing traitors. IEEE Transactions on Information Theory, 46(3), 893–910 (2000)CrossRefMATH
15.
M. Dietzfelbinger, C. Weidling, Balanced allocation and dictionaries with tightly packed constant size bins. Theor. Comput. Sci., 380(1-2), 47–68, (2007)MathSciNetCrossRefMATH
16.
M. Dietzfelbinger, P. Woelfel, Almost random graphs with simple hash functions, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 629–638 (2003)
17.
Y. Dodis, J.P. Steinberger, Domain extension for macs beyond the birthday barrier, in Advances in Cryptology—EUROCRYPT 2011, pp. 323–342 (2011)
18.
D. Fotakis, R. Pagh, P. Sanders, P.G. Spirakis, Space efficient hash tables with worst case constant access time. Theory Comput. Syst., 38(2), 229–248 (2005)MathSciNetCrossRefMATH
19.
A.M. Frieze, P. Melsted, M. Mitzenmacher, An analysis of random-walk cuckoo hashing. SIAM J. Comput., 40(2), 291–308 (2011)MathSciNetCrossRefMATH
20.
O. Goldreich, Towards a theory of software protection, in Advances in Cryptology—CRYPTO ’86, pp. 426–439 (1986)
21.
O. Goldreich, S. Goldwasser, S. Micali, On the cryptographic applications of random functions, in Advances in Cryptology—CRYPTO ’84, pp. 276–288 (1984)
22.
O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions. J. ACM, 792–807 (1986)
23.
24.
J. Håstad, R. Impagliazzo, L.A. Levin, M. Luby, A pseudorandom generator from any one-way function. SIAM J. Comput., 1364–1396 (1999)
25.
V.T. Hoang, B. Morris, P. Rogaway, An enciphering scheme based on a card shuffle, in Advances in Cryptology—CRYPTO 2012, pp. 1–13 (2012)
26.
A. Jain, K. Pietrzak, A. Tentes, Hardness preserving constructions of pseudorandom functions, in Theory of Cryptography, 9th Theory of Cryptography Conference, TCC 2012, pp. 369–382 (2012)
27.
D. Jetchev, O. Özen, M. Stam, Understanding adaptivity: Random systems revisited, in Advances in Cryptology – ASIACRYPT 2012, pp. 313–330 (2012)
28.
E. Kaplan, M. Naor, O. Reingold, Derandomized constructions of k-wise (almost) independent permutations. Algorithmica 55(1), 113–133 (2009)MathSciNetCrossRefMATH
29.
A. Kirsch, M. Mitzenmacher, U. Wieder, More robust hashing: Cuckoo hashing with a stash. SIAM J. Comput., 39(4), 1543–1561 (2009)MathSciNetCrossRefMATH
30.
31.
M. Luby, Pseudorandomness and cryptographic applications. Princeton computer science notes. (Princeton University Press, 1996)MATH
32.
M. Luby, C. Rackoff, How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2), 373–386 (1988)MathSciNetCrossRefMATH
33.
U.M. Maurer, Indistinguishability of random systems, in Advances in Cryptology—EUROCRYPT 2002, pp. 110–132 (2002)
34.
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, pp. 410–427 (2004)
35.
U.M. Maurer, S. Tessaro, Domain extension of public random functions: Beyond the birthday barrier, in Advances in Cryptology—CRYPTO 2007, pp. 187–204 (2007)
36.
B. Morris, P. Rogaway, Sometimes-recurse shuffle - almost-random permutations in logarithmic expected time, in Advances in Cryptology—EUROCRYPT 2014, pp. 311–326 (2014)
37.
B. Morris, P. Rogaway, T. Stegers, How to encipher messages on a small domain, in Advances in Cryptology—CRYPTO 2009, pp. 286–302 (2009)
38.
S. Myers, Black-box composition does not imply adaptive security, in Advances in Cryptology—EUROCRYPT 2004, pp. 189–206 (2004)
39.
M. Nandi, A unified method for improving prf bounds for a class of blockcipher based macs, in Fast Software Encryption, 17th International Workshop, FSE 2010, Seoul, Korea, pp. 212–229 (2010)
40.
M. Naor, O. Reingold, On the construction of pseudorandom permutations: Luby-rackoff revisited. Journal of Cryptology, 12(1), 29–66 (1999a)MathSciNetCrossRefMATH
41.
M. Naor, O. Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions. Journal of Computer and System Sciences, 58(2), 336–375 (1999b)MathSciNetCrossRefMATH
42.
M. Naor, O. Reingold, Constructing pseudo-random permutations with a prescribed structure. Journal of Cryptology, 15(2), 97–102, (2002)MathSciNetCrossRefMATH
43.
R. Ostrovsky, An efficient software protection scheme, in Advances in Cryptology—CRYPTO ’89 (1989)
44.
45.
46.
J. Patarin, Security of random feistel schemes with 5 or more rounds, in Advances in Cryptology—CRYPTO 2004, pp. 106–122 (2004)
47.
J. Patarin, A proof of security in o(2\(^{\text{n}}\)) for the benes scheme, in Progress in Cryptology— AFRICACRYPT 2008, pp. 209–220 (2008)
48.
J. Patarin, Security of balanced and unbalanced feistel schemes with linear non equalities. IACR Cryptology ePrint Archive, 2010, 293 (2010).
49.
K. Pietrzak, Composition does not imply adaptive security, in Advances in Cryptology—CRYPTO 2005, pp. 55–65 (2005)
50.
K. Pietrzak, Composition implies adaptive security in minicrypt, in Advances in Cryptology—EUROCRYPT 2006, pp. 328–338 (2006)
51.
52.
T. Ristenpart, S. Yilek, The mix-and-cut shuffle: Small-domain encryption secure against N queries, in Advances in Cryptology—CRYPTO 2013, pp. 392–409 (2013)
53.
A. Siegel, On universal classes of extremely random constant-time hash functions. SIAM Journal on Computing, 33(3), 505–543, (2004)MathSciNetCrossRefMATH
54.
M.N. Wegman, L. Carter, New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci., 22 (3), 265–279, (1981)MathSciNetCrossRefMATH
Metadata
Title
Hardness-Preserving Reductions via Cuckoo Hashing
Authors
Itay Berman
Iftach Haitner
Ilan Komargodski
Moni Naor
Publication date
07-05-2018
Publisher
Springer US
Published in
Journal of Cryptology / Issue 2/2019
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-018-9293-0

Other articles of this Issue 2/2019

Journal of Cryptology 2/2019 Go to the issue

OriginalPaper

Non-black-box Simulation in the Fully Concurrent Setting, Revisited

OriginalPaper

On Tight Security Proofs for Schnorr Signatures

OriginalPaper

Cryptanalysis of the CLT13 Multilinear Map

OriginalPaper

From Physical to Stochastic Modeling of a TERO-Based TRNG

OriginalPaper

Automated Analysis of Cryptographic Assumptions in Generic Group Models

OriginalPaper

Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting

Premium Partner

    Image Credits