nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Multi-Collision Resistant Hash Functions and Their Applications

verfasst von : Itay Berman, Akshay Degwekar, Ron D. Rothblum, Prashant Nalini Vasudevan

Erschienen in: Advances in Cryptology – EUROCRYPT 2018

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Collision resistant hash functions are functions that shrink their input, but for which it is computationally infeasible to find a collision, namely two strings that hash to the same value (although collisions are abundant).

In this work we study multi-collision resistant hash functions (\(\mathsf {MCRH}\)) a natural relaxation of collision resistant hash functions in which it is difficult to find a t-way collision (i.e., t strings that hash to the same value) although finding \((t-1)\)-way collisions could be easy. We show the following:

The existence of \(\mathsf {MCRH}\) follows from the average case hardness of a variant of the Entropy Approximation problem. The goal in this problem (Goldreich, Sahai and Vadhan, CRYPTO ’99) is to distinguish circuits whose output distribution has high entropy from those having low entropy.
\(\mathsf {MCRH}\) imply the existence of constant-round statistically hiding (and computationally binding) commitment schemes. As a corollary, using a result of Haitner et al. (SICOMP, 2015), we obtain a blackbox separation of \(\mathsf {MCRH}\) from any one-way permutation.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Sustained Space Complexity

Nächstes Kapitel Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions

We remark that the weaker notion of universal one-way hash functions (UOWHF) (which is known to be implied by standard one-way functions) suffices for this application [NY89, Rom90].

Recall that the Shannon Entropy of a random variable X is defined as

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-78375-8_5/466130_1_En_5_IEq57_HTML.gif

For a random variable X, the min-entropy is defined as

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-78375-8_5/466130_1_En_5_IEq62_HTML.gif

whereas the max-entropy is

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-78375-8_5/466130_1_En_5_IEq63_HTML.gif

In fact, [DGRV11] show that the same conclusion holds even if we restrict the problem to constant-depth (i.e.,

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-78375-8_5/466130_1_En_5_IEq83_HTML.gif

) circuits.

Given such a scheme consider a circuit that has, hard-coded inside, a pair of ciphertexts \((c_0,c_1)\) which are either encryptions of the same bit or of different bits. The circuit gets as input a bit b and random string r and outputs a re-randomization of \(c_b\) (using randomness r). If the scheme is perfectly re-randomizing (and perfectly correct) then the min-entropy of the output distribution in case the plaintexts disagree is larger than the max-entropy in case the plaintexts agree.

The hard distribution for \( \mathsf {SVP}_{\sqrt{n}} \) and \( \mathsf {CVP}_{\sqrt{n}} \) is the first message from the 2-message honest-verifier

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-78375-8_5/466130_1_En_5_IEq90_HTML.gif

proof system of Goldreich and Goldwasser [GG98]. In the case of \( \mathsf {CVP}_{\sqrt{n}} \), the input is (B, t, d) where B is the basis of the lattice, t is a target vector and d specifies the bound on the distance of t from the lattice. The distribution is obtained by sampling a random error vector \( \eta \) from the ball of radius \( d\sqrt{n}/2 \) centered at the origin and outputting \( b\cdot t + \eta \mod \mathcal {P}(B) \), where

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-78375-8_5/466130_1_En_5_IEq95_HTML.gif

and \( \mathcal {P}(B) \) is the fundamental parallelopiped of B. When t is far from the lattice, this distribution is injective and hence has high min-entropy while when t is close to the lattice, the distribution is not injective and hence has lower max-entropy. Similarly for \( \mathsf {SVP}_{\sqrt{n}} \), on input (B, d), the output is \( \eta \mod \mathcal {P}(B) \) where \( \eta \) is again sampled from a ball of radius \( d\sqrt{n}/2 \).

Note that the graph isomorphism is known to be solvable in polynomial-time for many natural distributions, and the recent breakthrough result of Babai [Bab16] gives a quasi-polynomial worst-case algorithm. Nevertheless, it is still plausible that Graph Isomorphism is average-case quasi-polynomially hard (for some efficiently samplable distribution).

The trapdoor to the lossy function is not used in the construction of \( \mathsf {CRH}\).

In contrast, it is easy to see that repetition amplifies the additive gap between the min-entropy and the max-entropy. In fact, we use this in our construction.

Actually, Ong and Vadhan [OV08] only construct instance-dependent commitments. Dvir et al. [DGRV11] attribute the construction of constant-round statistically hiding commitments from average-case hardness of

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-78375-8_5/466130_1_En_5_IEq127_HTML.gif

to a combination of [OV08] and an unpublished manuscript of Guy Rothblum and Vadhan [RV09].

This setting (and construction) is similar to that of Peikert and Waters’s construction of \( \mathsf {CRH}\) from lossy functions [PW11].

Recall that a collection of functions \(\mathcal {F}\) is k-wise independent if for every distinct \(x_1,\ldots ,x_k\), the distribution of \((f(x_1),\ldots ,f(x_k))\) (over the choice of \(f \leftarrow \mathcal {F}\)) is uniform.

We remark that more efficient constructions are known, see Remark 2.4.

We remark that our construction of \(\mathsf {MCRH}\) based on \(\mathsf {EA}_{\min ,\max }^{}\) (see Sect. 3) actually supports such large shrinkage.

In a nutshell, the property that we are using is that if \(N=3^k\) balls are thrown into N bins, with high probability the maximal load in every bin will be at most \(\log (N)\). It is well-known that hash functions that are \(\log (N)\)-wise independent also have this property. See Sect. 2.2 for details.

The general construction of statistically-hiding commitments from inaccessible entropy generators is meant to handle a much more general case than the one needed in our setting. In particular, a major difficulty handled by [HRVW09, HV17] is when the generator has many blocks and it is not known in which one there is a gap between the real and accessible entropies.

[ADM+99]

Alon, N., Dietzfelbinger, M., Miltersen, P.B., Petrank, E., Tardos, G.: Linear hash functions. J. ACM 46(5), 667–683 (1999)MathSciNetCrossRefMATH

[AR16]

Applebaum, B., Raykov, P.: On the relationship between statistical zero-knowledge and statistical randomized encodings. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 449–477. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_16CrossRef

[Bab16]

Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: Wichs, D., Mansour, Y. (eds.) Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18–21 June 2016, pp. 684–697. ACM (2016)

[BDRV17]

Berman, I., Degwekar, A., Rothblum, R.D., Vasudevan, P.N.: Multi collision resistant hash functions and their applications. IACR Cryptology ePrint Archive 2017, 489 (2017)

[BPK17]

Bitansky, N., Paneth, O., Kalai, Y.T.: Multi-collision resistance: A paradigm for keyless hash functions. Electron. Colloquium Comput. Complex. (ECCC) 24, 99 (2017)

[BPVY00]

Brickell, E., Pointcheval, D., Vaudenay, S., Yung, M.: Design Validations for Discrete Logarithm Based Signature Schemes. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 276–292. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-540-46588-1_19CrossRef

[CRSW13]

Elisa Celis, L., Reingold, O., Segev, G., Wieder, U.: Balls and bins: smaller hash families and faster evaluation. SIAM J. Comput. 42(3), 1030–1050 (2013)

[DGRV11]

Dvir, Z., Gutfreund, D., Rothblum, G.N., Vadhan, S.P.: On approximating the entropy of polynomial mappings. In: Proceedings of Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, 7–9 January 2011, pp. 460–475 (2011)

[DHRS07]

Ding, Y.Z., Harnik, D., Rosen, A., Shaltiel, R.: Constant-round oblivious transfer in the bounded storage model. J. Cryptol. 20(2), 165–202 (2007)

[DI06]

Dubrov, B., Ishai, Y.: On the randomness complexity of efficient sampling. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 711–720. ACM (2006)

[DPP93]

Damgård, I.B., Pedersen, T.P., Pfitzmann, B.: On the existence of statistically hiding bit commitment schemes and fail-stop signatures. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 250–265. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_22

[GG98]

Goldreich, O., Goldwasser, S.: On the limits of non-approximability of lattice problems. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 1–9. ACM (1998)

[GMR88]

Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)MathSciNetCrossRefMATH

[GS94]

Girault, M., Stern, J.: On the length of cryptographic hash-values used in identification schemes. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 202–215. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48658-5_21

[GSV99]

Goldreich, O., Sahai, A., Vadhan, S.: Can statistical zero knowledge be made non-interactive? or on the relationship of SZK and NISZK. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 467–484. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_30CrossRef

[HHRS15]

Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols—tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput. 44(1), 193–242 (2015)MathSciNetCrossRefMATH

[HM96]

Halevi, S., Micali, S.: Practical and provably-secure commitment schemes from collision-free hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201–215. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_16

[HNO+09]

Haitner, I., Nguyen, M.-H., Ong, S.J., Reingold, O., Vadhan, S.P.: Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput. 39(3), 1153–1218 (2009)

[HR04]

Hsiao, C.-Y., Reyzin, L.: Finding collisions on a public road, or do secure hash functions need secret coins? In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 92–105. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_6CrossRef

[HRVW09]

Haitner, I., Reingold, O., Vadhan, S.P., Wee, H.: Inaccessible entropy. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, 31 May-2 June 2009, pp. 611–620 (2009)

[HV17]

Haitner, I., Vadhan, S.: The many entropies in one-way functions. Tutorials on the Foundations of Cryptography. ISC, pp. 159–217. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57048-8_4CrossRef

[Jou04]

Joux, A.: Multicollisions in iterated hash functions. Application to cascaded constructions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_19CrossRef

[Kil92]

Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 4–6 May 1992, pp. 723–732 (1992)

[KNY17a]

Komargodski, I., Naor, M., Yogev, E.: Collision resistant hashing for paranoids: dealing with multiple collisions. IACR Cryptology ePrint Archive 2017, 486 (2017)

[KNY17b]

Komargodski, I., Naor, M., Yogev, E.: White-box vs. black-box complexity of search problems: ramsey and graph property testing. Electron. Colloquium Comput. Complex. (ECCC) 24, 15 (2017)

[Mer89]

Merkle, R.C.: One way hash functions and DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428–446. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_40CrossRef

[Mic00]

Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253–1298 (2000)MathSciNetCrossRefMATH

[MRRR14]

Meka, R., Reingold, O., Rothblum, G.N., Rothblum, R.D.: Fast pseudorandomness for independence and load balancing. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 859–870. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43948-7_71

[NY89]

Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, Washigton, USA, 14–17 May 1989, pp. 33–43 (1989)

[Ost91]

Ostrovsky, R.: One-way functions, hard on average problems, and statistical zero-knowledge proofs. In: Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, 30 June-3 July 1991, pp. 133–138 (1991)

[OV08]

Ong, S.J., Vadhan, S.: An equivalence between zero knowledge and commitments. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 482–500. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_27CrossRef

[PRS12]

Pietrzak, K., Rosen, A., Segev, G.: Lossy functions do not amplify well. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 458–475. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_26CrossRef

[PW11]

Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. SIAM J. Comput. 40(6), 1803–1844 (2011)MathSciNetCrossRefMATH

[Rom90]

Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, Maryland, USA, 13–17 May 1990, pp. 387–394 (1990)

[RS96]

Rivest, R.L., Shamir, A.: Payword and micromint: two simple micropayment schemes. In: Proceedings of Security Protocols, International Workshop, Cambridge, United Kingdom, 10–12 April 1996, pp. 69–87 (1996)

[RTV04]

Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_1CrossRef

[RV09]

Rothblum, G.N., Vadhan, S.P.: Unpublished Manuscript (2009)

[Sim98]

Simon, D.R.: Finding collisions on a one-way street: can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054137CrossRef

[Vad12]

Vadhan, S.P.: Pseudorandomness. Found. Trends Theor. Comput. Sci. 7(1–3), 1–336 (2012)MathSciNetCrossRefMATH

Titel: Multi-Collision Resistant Hash Functions and Their Applications
verfasst von: Itay Berman
Akshay Degwekar
Ron D. Rothblum
Prashant Nalini Vasudevan
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2018
Print ISBN: 978-3-319-78374-1

Electronic ISBN: 978-3-319-78375-8

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-78375-8_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"