Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2016 | OriginalPaper | Buchkapitel

From Indifferentiability to Constructive Cryptography (and Back)

verfasst von : Ueli Maurer, Renato Renner

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

The concept of indifferentiability of systems, a generalized form of indistinguishability, was proposed in 2004 to provide a simplified and generalized explanation of impossibility results like the non-instantiability of random oracles by hash functions due to Canetti, Goldreich, and Halevi (STOC 1998). But indifferentiability is actually a constructive notion, leading to possibility results. For example, Coron et al. (Crypto 2005) argued that the soundness of the construction C(f) of a hash function from a compression function f can be demonstrated by proving that C(R) is indifferentiable from a random oracle if R is an ideal random compression function.
The purpose of this short paper is to describe how the indifferentiability notion was a precursor to the theory of constructive cryptography and thereby to provide a simplified and generalized treatment of indifferentiability as a special type of constructive statement.

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
Nächstes Kapitel Fast Pseudorandom Functions Based on Expander Graphs
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Formally, the constructor \(\gamma \) on the right side might involve some scheme for addressing the resource specified by \(\mathcal{R}\) among all resources, and in this case it would have to be an adequately modified version of \(\gamma \) on the left side (i.e., in \(\mathcal{R}\mathop {\longrightarrow }\limits ^{\gamma } \mathcal{S}\)).
 
2
The term “converter” is used because its application at an interface converts the interface into an interface with a different behavior.
 
3
In general, one could consider partial function where the application of a converter at an interface need not always be defined. For the purpose of this paper there is no need to consider partial functions.
 
4
For a logical predicate P, the purpose of a statement of the form \(\exists x\;P(x)\) is precisely to ignore which x makes P(x) true.
 
5
In this model, the memory required for a function computation is assumed to be free. Of course, one could also model this memory as a resource.
 
6
More formally, converters \(\alpha \) and \(\beta \) from this particular set \(\varSigma \) can be composed to a new converter, say \(\alpha \circ \beta \), and this composition is closed in the sense that the function \(\varPhi \rightarrow \varPhi \) induced by \(\alpha \circ \beta \) is contained in the class of functions induced by converters in \(\varSigma \).
 
7
To keep the presentation simple we assume that the probability distribution of Z is uniform; a generalization to arbitrary probability distributions is straightforward. This includes the case where \(\mathrm {PR}^{k}\) is a fixed hash function program of length k.
 
8
One may impose the additional restriction that the string Z can only be read bit-wise, but this is not relevant for the considerations here.
 
9
That is, \(d(R, S) = \sup _{D \in \mathcal {D}} \varDelta ^D(R, S)\), where \(\varDelta ^D(R, S)\) is the absolute value of the difference between the probability that D returns 0 when connected to R and the probability that it returns 0 when connected to S.
 
10
The result in [9] corresponding to Theorem 2 is weaker in that the error \(\epsilon \) is multiplied with \(\ell ^2\) rather than \(\ell \).
 
11
Proposition 1 is a corollary of Theorem 1 of [25].
 
Literatur
1.
Andreeva, E., Mennink, B., Preneel, B.: On the indifferentiability of the Grøstl hash function. In: Garay, J.A., Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 88–105. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-15317-4_​7 CrossRef
2.
Bertoni, G., Daemen, J., Peeters, M., Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-78967-3_​11 CrossRef
3.
4.
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
5.
Canetti, R., Universally composable security: a new paradigm for cryptographic protocols. In: Proceedings of the 42nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2001, pp. 136–145. IEEE Computer Society Press, October 2001. Full version, http://​eprint.​iacr.​org/​2000/​067
6.
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC 1998, pp. 209–218. ACM (1998)
7.
8.
Coretti, S., Maurer, U., Tackmann, B.: Constructing confidential channels from authenticated channels—public-key encryption revisited. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8269, pp. 134–153. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-42033-7_​8 CrossRef
9.
Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgård revisited: how to construct a hash function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005). doi:10.​1007/​11535218_​26 CrossRef
10.
Demay, G., Gaži, P., Hirt, M., Maurer, U.: Resource-restricted indifferentiability. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 664–683. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38348-9_​39 CrossRef
11.
Dodis, Y., Reyzin, L., Rivest, R.L., Shen, E.: Indifferentiability of permutation-based compression functions and tree-based modes of operation, with applications to MD6. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 104–121. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-03317-9_​7 CrossRef
12.
Dodis, Y., Ristenpart, T., Steinberger, J., Tessaro, S.: To hash or not to hash again? (In)Differentiability results for \(H^{2}\) and HMAC. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 348–366. Springer, Heidelberg (2012)CrossRef
13.
König, R., Renner, R.: Sampling of min-entropy relative to quantum knowledge. IEEE Trans. Inf. Theor. 57, 4760–4787 (2011)MathSciNetCrossRef
14.
König, R., Renner, R., Schaffner, C.: The operational meaning of min- and max-entropy. IEEE Trans. Inf. Theor. 55, 4337–4347 (2009)MathSciNetCrossRef
15.
16.
Maurer, U.: Constructive cryptography - a new paradigm for security definitions and proofs. In: Moedersheim, S., Palamidessi, C. (eds.) TOSCA 2011. LNCS, vol. 6993, pp. 33–56. Springer, Heidelberg (2011)CrossRef
17.
Maurer, U., Renner, R.: Abstract cryptography. In: Chazelle, B. (ed.) The Second Symposium on Innovations in Computer Science, ICS 2011, pp. 1–21. Tsinghua University Press, January 2011
18.
Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random Oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-24638-1_​2 CrossRef
19.
Maurer, U., Rüedlinger, A., Tackmann, B.: Confidentiality and integrity: a constructive perspective. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 209–229. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-28914-9_​12 CrossRef
20.
Maurer, U., Tackmann, B.: On the soundness of authenticate-then-encrypt: formalizing the malleability of symmetric encryption. In: Proceedings of the 17th ACM Conference on Computer and Communication Security (ACM-CCS), pp. 505–515. ACM, October 2010
21.
22.
Portmann, C., Matt, C., Maurer, U., Renner, R., Tackmann, B., Boxes, C.: Quantum information-processing systems closed under composition. eprint, arXiv:​1512.​02240 (2016)
23.
Ristenpart, T., Shacham, H., Shrimpton, T.: Careful with composition: limitations of the indifferentiability framework. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 487–506. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20465-4_​27 CrossRef
24.
Vadhan, S.P.: On constructing locally computable extractors and cryptosystems in the bounded storage model. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 61–77. Springer, Heidelberg (2003). doi:10.​1007/​978-3-540-45146-4_​4 CrossRef
25.
Wullschleger, J.: Bitwise quantum min-entropy sampling and new lower bounds for random access codes. In: Bacon, D., Martin-Delgado, M., Roetteler, M. (eds.) TQC 2011. LNCS, vol. 6745, pp. 164–173. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-54429-3_​11 CrossRef
Metadaten
Titel
From Indifferentiability to Constructive Cryptography (and Back)
verfasst von
Ueli Maurer
Renato Renner
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Theory of Cryptography

Print ISBN: 978-3-662-53640-7

Electronic ISBN: 978-3-662-53641-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53641-4_1