nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Classical Proofs for the Quantum Collapsing Property of Classical Hash Functions

verfasst von : Serge Fehr

Erschienen in: Theory of Cryptography

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

Hash functions are of fundamental importance in theoretical and in practical cryptography, and with the threat of quantum computers possibly emerging in the future, it is an urgent objective to understand the security of hash functions in the light of potential future quantum attacks. To this end, we reconsider the collapsing property of hash functions, as introduced by Unruh, which replaces the notion of collision resistance when considering quantum attacks. Our contribution is a formalism and a framework that offers significantly simpler proofs for the collapsing property of hash functions. With our framework, we can prove the collapsing property for hash domain extension constructions entirely by means of decomposing the iteration function into suitable elementary composition operations. In particular, given our framework, one can argue purely classically about the quantum-security of hash functions; this is in contrast to previous proofs which are in terms of sophisticated quantum-information-theoretic and quantum-algorithmic reasoning.

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 Secure Certification of Mixed Quantum States with Application to Two-Party Randomness Generation

Nächstes Kapitel Traitor-Tracing from LWE Made Simple and Attribute-Based

Nur mit Berechtigung zugänglich

This again implies security in the random oracle model, but a subtle issue here is that if the round function is efficiently invertible then the assumptions on the two parts are not satisfied. Hence, this is not so strong evidence yet that e.g. SHA-3 is collapsing.

The latter is because (our notion of) the disjoint union of two functions requires not only the two respective domains but also the two respective ranges to be disjoint.

For simplicity, we consider one block of output only; multiple output blocks are argued by means of composition too.

This can be understood in that quantum operations may “abort”, and the trace \(\mathrm {tr}(\rho ) \le 1\) expresses the probability that the process that produces \(\rho \) does not abort.

This bound can e.g. be derived from [8]. [2] claims the bound \(\sqrt{\beta }\), but their proof has a small flaw; fixing it gives \(\sqrt{2\beta }\) instead (but only works for total measurements). .

A subtle issue with this notation is that \(\mathrm {tr}_Y(\rho _{Xf(X)Z}) \ne \rho _{XZ}\), but rather

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-03810-6_12/476307_1_En_12_IEq105_HTML.gif

(see below).

See the discussion in Appendix C for an exception to the rule.

We recall that the requirement \(\rho _{XYE} = \rho _{X h(X) E}\) is a shorthand for asking \(\rho _{XYE}\) to be equal to a state obtained by applying

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-03810-6_12/476307_1_En_12_IEq161_HTML.gif

to system X.

This may be understood in that the computation of h “fails” on inputs not in \(\mathcal{X}_\text {eff}\).

I.e.,

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-03810-6_12/476307_1_En_12_IEq222_HTML.gif

first performs the measurement

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-03810-6_12/476307_1_En_12_IEq223_HTML.gif

, and then measures the resulting state in the computation basis if (and only if) the measurement outcome was 0.

Since the bit size of the input to \({ M\!D}\) must be an integer multiple of r, the Merkle-Damgård construction usually comes with a padding that maps a string of arbitrary size into a sequence of blocks of bit size r. We can safely ignore this since any injective padding preserves the collapsing property by Lemma 5.

Here, we understand \(\pi _{i-1}\) as \(\pi _{i-1}: \dot{\mathcal{X}}_i \rightarrow \{0,1\}\), \((x_1,\ldots ,x_i) \mapsto \pi _{i-1}(x_1,\ldots ,x_{i-1})\).

Even though our definition of the collapsing property differs slightly from the definition in [5], these differences disappear in such asymptotic statements, as discussed in Sect. 3. See also Appendix C.

For the purpose of collisions and the collapsing property, we can think of the salt simply as part of the input: we do not want collisions even for different choices of the salt.

Like for Merkle-Damgård, we can safely ignore the padding here.

Here, we understand \(\pi _{i-1}\) as \(\pi _{i-1}: \dot{\mathcal{X}}_i \rightarrow \{0,1\}\), \((x_1,\ldots ,x_i) \mapsto \pi _{i-1}(x_1,\ldots ,x_{i-1})\).

For the latter, one could actually consider both simultaneously.

Meaning that for any \(\mathcal{X}' \supset \mathcal{X}\), the function \(\mathcal{X}' \rightarrow \{0,1\}\) that maps \(x \in \mathcal{X}\) to 1 and \(x \in \mathcal{X}'\setminus \mathcal{X}\) to 0 has zero complexity. This is trivially satisfied for any function f in case of \(\mathfrak {c}^\mathsf{query}\) (given in Example 2).

This is in line with our interpretation of \(\mathrm {tr}(\rho ) < 1\) as capturing an “abort” of the preparation process.

Remember that we want XOR’s to be “for free”.

As a matter of fact, [6, Definition 8] considers a t-fold parallel repetition of the game, where t is an additional parameter of the definition. We ignore this for the discussion here, recalling that we obtain immediately a similar variant of our definition by means of concurrent composition.

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_11CrossRef

Czajkowski, J., Groot Bruinderink, L., Hülsing, A., Schaffner, C., Unruh, D.: Post-quantum security of the sponge construction. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 185–204. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_9CrossRefMATH

Biham, E., Dunkelman, O.: A framework for iterative hash functions – HAIFA. In: Second NIST Cryptographic Hash Workshop (2006). https://eprint.iacr.org/2007/278.pdf

Hülsing, A., Rijneveld, J., Song, F.: Mitigating multi-target attacks in hash-based signatures. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9614, pp. 387–416. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7_15CrossRef

Unruh, D.: Computationally binding quantum commitments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 497–527. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_18CrossRef

Unruh, D.: Collapse-binding quantum commitments without random oracles. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 166–195. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_6CrossRef

Winter, A.: Coding theorem and strong converse for quantum channels. IEEE Trans. Inf. Theory 45(7), 2481–2485 (1999). https://arxiv.org/abs/1409.2536MathSciNetCrossRef

Wilde, M.: From Classical to Quantum Shannon Theory, 2nd edn. (2016). https://arxiv.org/abs/1106.1445. Manuscript

Titel: Classical Proofs for the Quantum Collapsing Property of Classical Hash Functions
verfasst von: Serge Fehr
Verlag: Springer International Publishing
Buch: Theory of Cryptography
Print ISBN: 978-3-030-03809-0

Electronic ISBN: 978-3-030-03810-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-03810-6_12

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"

Premium Partner