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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

On the Power of Hierarchical Identity-Based Encryption

verfasst von : Mohammad Mahmoody, Ameer Mohammed

Erschienen in: Advances in Cryptology – EUROCRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We prove that there is no fully black-box construction of collision-resistant hash functions (CRH) from hierarchical identity-based encryption (HIBE) with arbitrary polynomial number of identity levels. To the best of our knowledge this is the first limitation proved for HIBE. As a corollary, we obtain a series of separations that are not directly about HIBE or CRH but are interesting on their own right. Namely, we show that primitives such as IBE and CCA-secure public-key encryption cannot be used in a black-box way to construct fully homomorphic encryption or any primitive that implies CRH in a black-box way.
Our proof relies on the reconstruction paradigm of Gennaro and Trevisan (FOCS 2000) and Haitner et al. (FOCS 2007) and extends their techniques for one-way and trapdoor permutations to the setting of HIBE. A main technical challenge in the proof of our separation stems from the adaptivity of the HIBE adversary who is allowed to obtain keys for different identities before she selects the attacked identity. Our main technical contribution is to develop compression/reconstruction techniques that can be achieved relative to such adaptive attackers.

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 All Complete Functionalities are Reversible
Nächstes Kapitel On the Impossibility of Tight Cryptographic Reductions
Fußnoten
1
We shall also note that even the techniques behind the proof of [23] do not seem to extend to a separation of CCA secure encryption from TDPs, even though CCA secure encryption could be constructed from TDP and random oracles [3]. The reason is that the “collision finding oracle” (see Definition 9) of [23, 45] prevents the random TDP oracle from being independent of the other subroutines of the oracle to be used as a random oracle.
 
2
Statistically hiding commitment is known to be implied by CRH [12, 35] and so proving separation for statistically hiding commitment is stronger than a similar result for CRH.
 
3
In fact [15] achieves exponential compression and doubly exponentially small probability of success for a fixed A. This lets them do a union bound over all poly-sized circuits A when \(\pi \) is chosen at random.
 
4
By the Goldreich Levin lemma [20] these two notions of security are equivalent in a black-box way.
 
5
Note that we define a key generation algorithm for each level (as opposed to a single algorithm) in order to simplify our HIBE construction using our ideal oracle.
 
6
Some of the subsequent definitions of HIBE use a more general definition in which one can encrypt messages under partial identity vectors \(\mathrm {ID}_i = \langle id_0,...,id_i \rangle \) of depth \(i<\ell \). Our impossibility result directly extends to this more general setting as well. However, for sake of simplicity here we focus on the original definition of [25].
 
7
In this work we focus on using the simpler collision finding oracle that is not interactive. However, all of our separation results hold with respect to the stronger Sam oracle of “low” (i.e., \(o(n / \log n)\)) as well. We refer the proof for the more general case to the full version [32] of the paper.
 
8
Note that the returned “collision” \((x,x')\) is not necessarily distributed like a uniformly sampled collision from all possible collisions.
 
9
The actual argument is more subtle, but the main idea is the linearity of expectation over different probabilities.
 
Literatur
1.
Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010)CrossRef
2.
Asharov, G., Segev, G.: Limits on the power of indistinguishability obfuscation and functional encryption. Cryptology ePrint Archive, Report 2015/341 (2015). http://​eprint.​iacr.​org/​
3.
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)
4.
Boneh, D., Boyen, X.: Efficient selective-ID secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)CrossRef
5.
Boneh, D., Boyen, X., Goh, E.-J.: Hierarchical identity based encryption with constant size ciphertext. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 440–456. Springer, Heidelberg (2005)CrossRef
6.
Boneh, D., Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. SIAM J. Comput. 36(5), 1301–1328 (2006)MathSciNetCrossRefMATH
7.
8.
Boneh, D., Papakonstantinou, P.A., Rackoff, C., Vahlis, Y., Waters, B.: On the impossibility of basing identity based encryption on trapdoor permutations. In: FOCS, pp. 283–292. IEEE Computer Society (2008)
9.
Boneh, D., Sahai, A., Waters, B.: Functional encryption: definitions and challenges. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 253–273. Springer, Heidelberg (2011)CrossRef
10.
Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 255–271. Springer, Heidelberg (2003)CrossRef
11.
Chung, K.-M., Lin, H., Mahmoody, M., Pass, R.: On the power of nonuniformity in proofs of security. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pp. 389–400. ACM (2013)
12.
Damgård, I.B., Pedersen, T.P., Pfitzmann, B.: On the existence of statistically hiding bit commitment schemes and fail-stop signatures. J. Cryptol. 10(3), 163–194 (1997)MathSciNetCrossRefMATH
13.
Gennaro, G., Katz.: Lower bounds on the efficiency of encryption and digital signature schemes. In: STOC: ACM Symposium on Theory of Computing (STOC) (2003)
14.
Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput. 35(1), 217–246 (2005)MathSciNetCrossRefMATH
15.
Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: FOCS, pp. 305–313 (2000)
16.
17.
Gentry, C., Silverberg, A.: Hierarchical ID-based cryptography. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 548–566. Springer, Heidelberg (2002)CrossRef
18.
Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: FOCS, pp. 325–335 (2000)
19.
20.
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of \(21\)st STOC, pp. 25–32. ACM (1989)
21.
22.
Goyal, V., Kumar, V., Lokam, S., Mahmoody, M.: On black-box reductions between predicate encryption schemes. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 440–457. Springer, Heidelberg (2012)CrossRef
23.
Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - a tight lower bound on the round complexity of statistically-hiding commitments. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS ), 20–23 October 2007, Providence, RI, USA, pp. 669–679. IEEE Computer Society (2007)
24.
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)MathSciNetCrossRefMATH
25.
Horwitz, J., Lynn, B.: Toward hierarchical identity-based encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 466–481. Springer, Heidelberg (2002)CrossRef
26.
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)CrossRef
27.
Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: FOCS, pp. 230–235 (1989)
28.
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 44–61. ACM Press (1989)
29.
Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Sufficient conditions for collision-resistant hashing. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 445–456. Springer, Heidelberg (2005)CrossRef
30.
Lindell, Y.: A simpler construction of CCA2-secure public-key encryption under general assumptions. J. Cryptol. 19(3), 359–377 (2006)MathSciNetCrossRefMATH
31.
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)MathSciNetCrossRefMATH
32.
33.
Maurer, U.M., Yacobi, Y.: Non-interactive public-key cryptography. In: Davies, D.W. (ed.) Advances in Cryptology EUROCRYPT 1991. LNCS, vol. 547, pp. 498–507. Springer, Heidelberg (1991)
34.
35.
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 (STOC), pp. 33–43. ACM Press (1989)
36.
Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings of the 22nd STOC, pp. 427–437. ACM Press (1990)
37.
Naor, M., Ziv, A.: Primary-secondary-resolver membership proof systems. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 199–228. Springer, Heidelberg (2015)CrossRef
38.
Pandey, O., Pass, R., Vaikuntanathan, V.: Adaptive one-way functions and applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 57–74. Springer, Heidelberg (2008)CrossRef
39.
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC: ACM Symposium on Theory of Computing (STOC) (2005)
40.
Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004)CrossRef
41.
Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: STOC, pp. 387–394 (1990)
42.
Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 543–553 (1999)
43.
Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005)CrossRef
44.
Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)CrossRef
45.
Simon, D.R.: Findings 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)CrossRef
46.
Unruh, D.: Random oracles and auxiliary input. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 205–223. Springer, Heidelberg (2007)CrossRef
47.
48.
Yao, A.C.: Theory and applications of trapdoor functions. In: Proceedings of the 23rd FOCS, pp. 80–91. IEEE (1982)
Metadaten
Titel
On the Power of Hierarchical Identity-Based Encryption
verfasst von
Mohammad Mahmoody
Ameer Mohammed
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – EUROCRYPT 2016

Print ISBN: 978-3-662-49895-8

Electronic ISBN: 978-3-662-49896-5

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-49896-5_9

Premium Partner

    Bildnachweise