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
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Identity-Based Encryption from the Diffie-Hellman Assumption

verfasst von : Nico Döttling, Sanjam Garg

Erschienen in: Advances in Cryptology – CRYPTO 2017

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We provide the first constructions of identity-based encryption and hierarchical identity-based encryption based on the hardness of the (Computational) Diffie-Hellman Problem (without use of groups with pairings) or Factoring. Our construction achieves the standard notion of identity-based encryption as considered by Boneh and Franklin [CRYPTO 2001]. We bypass known impossibility results using garbled circuits that make a non-black-box use of the underlying cryptographic primitives.

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 Watermarking Cryptographic Functionalities from Standard Lattice Assumptions
Nächstes Kapitel The First Collision for Full SHA-1
Fußnoten
1
The notion of chameleon hashing is closely related to the notion of chameleon commitment scheme [15] and we refer the reader to [34] for more discussion on this.
 
2
The success of decryption is conditioned on certain requirements placed on \((\mathsf {x},r)\). This restricted decryption capability is reminiscent of the concepts of witness encryption [22] and extractable witness encryption [4, 14].
 
3
In Sect. 5, we explain our constructions of chameleon encryption based on the (Computational) Diffie-Hellman Assumption, or the Factoring Assumption.
 
4
We use \(\epsilon \) to denote the empty string.
 
5
We note that our key generation mechanism can be seen as an instantiation of the Naor and Yung [40] tree-based construction of signature schemes from universal one-way hash functions and one-time signatures. This connection becomes even more apparent in the follow up paper [21].
 
6
For this part of the intuition, we assume familiarity with garbled circuits.
 
7
We use this notion only when the sampling can be done by a PPT algorithm and the sampling algorithm is implicit.
 
8
Typical definitions of garbled circuits do not require the length of each input label to be \(\lambda \) bits long. This additional requirement is crucial in our constructions as we chain garbled circuits. Note that input labels in any garbled circuit construction can always be shrunk to \(\lambda \) bits using a pseudorandom function.
 
9
In abuse of notation we assume that \(\mathsf {Sim}\) knows the (non-private) circuit C. When C has (private) hardwired inputs, we assume that the labels corresponding to these are included in the garbled circuit \(\tilde{C}\).
 
10
\(\mathsf {ct}\) is assumed to contain \((\mathsf {h},i,b)\).
 
11
Typically, Chameleon Hash functions are defined to also have the collision resilience property. This property is implied by the semantic security requirement below. However, we do not need this property directly. Therefore, we do not explicitly define it here.
 
12
We will later provide instantiations of \(\mathbb {G}\) which are of prime order and composite order. The use of \(\mathsf {Sample}(\mathbb {G})\) procedure is done to unify these two instantiations.
 
13
We also implicitly include the public and secret parameters for the group \(\mathbb {G}\) in \(\mathsf {k}\) and \(\mathsf {t}\) respectively.
 
14
We assume that the \(\mathsf {HardCore}(g^{ab})\) is a hardcore bit of \(g^{ab}\) given \(g^a\) and \(g^b\). If a deterministic hard-core bit for the specific function is not known then we can always use the Goldreich-Levin [30] construction. We skip the details of that with the goal of keeping exposition simple.
 
15
A prime number \(P > 2\) is called safe prime if \((P-1)/2\) is also prime.
 
16
The algorithm \(\mathsf {G}\) takes as input the security parameter \(1^\lambda \) and generates encryption key and decryption key pair \(\mathsf {ek}\) and \(\mathsf {dk}\) respectively, where the encryption key \(\mathsf {ek}\) is assumed to be \(\lambda \) bits long. The encryption algorithm \(\mathsf {E}(\mathsf {ek},\mathsf {m})\) takes as input an encryption key \(\mathsf {ek}\) and a message \(\mathsf {m}\) and outputs a ciphertext \(\mathsf {ct}\). Finally, the decryption algorithm \(\mathsf {D}(\mathsf {dk},\mathsf {ct})\) takes as input the secret key and the ciphertext and outputs the encrypted message \(\mathsf {m}\).
 
17
The IBE scheme defined in Sect. 3 does not fix the length of identities that it can be used with. However, in this section we fix the length of identities at setup time and use appropriately changed definitions. Looking ahead, the HIBE construction in Sect. 7 works for identities of arbitrary length.
 
18
Random coins used by these circuits are hardwired in them. For simplicity, we do not mention them explicitly.
 
19
\(\mathsf {F}(s,\varepsilon )\) is set to output s.
 
20
The trapdoor for the global hash function is not needed in the construction or the proof and is therefore dropped.
 
21
HIBE is often defined to have separate \(\mathsf {KeyGen}\) and \(\mathsf {Delegate}\) algorithms. For simplicity, we describe our scheme with just one \(\mathsf {KeyGen}\) algorithm that enables both the tasks of decryption and delegation. Secret-keys without delegation capabilities can be obtained by dropping the third entry (the PRG seed) from \(\mathsf {sk}_{\mathsf {id}}\).
 
22
For \(i < n\), \(z_\mathsf {v}\) will become the \(x_\mathsf {v}\) in next iteration.
 
23
The experiment can provide \(\mathsf {F}(s,\mathsf {id}^*)\) even though it does not appear in any of the \(\mathcal {A}\)’s secret key queries. The reason is that \(\mathsf {F}(s,\mathsf {id}^*)\) allows the capabilities of delegation but not decryption for ciphertexts to identity \(\mathsf {id}^*\).
 
24
Observe that these are specifically the cases in which one or two of the values \(s_1,s_2\) and \(s_3\) given as input to \(\mathsf {NodeGen}\) and \(\mathsf {NodeGen}'\) depend on the \(\{c_i\}\) values.
 
25
Note that since the adversary never makes a \(\mathsf {KeyGen}\) query for an identity \(\mathsf {id}\) that is a prefix of \(\mathsf {id}^*\). Therefore, we have that \(\mathsf {dk}_{\mathsf {v}}\) for \(\mathsf {v}\in V^*\cup \{\mathsf {id}^*\}\) will not be provided to \(\mathcal {A}\).
 
Literatur
1.
2.
Agrawal, S., Boneh, D., Boyen, X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 98–115. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14623-7_​6 CrossRef
3.
Agrawal, S., Boyen, X.: Identity-based encryption from lattices in the standard model. Manuscript (2009)
4.
5.
Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) ACM CCS 2012, pp. 784–796. ACM Press, Raleigh, 16–18 October 2012
6.
Bellare, M., Rogaway, P., Random oracles are practical: a paradigm for designing efficient protocols. In: Ashby, V. (ed.) ACM CCS 1993, pp. 62–73. ACM Press, Fairfax, 3–5 November 1993
7.
8.
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). doi:10.​1007/​978-3-540-24676-3_​14 CrossRef
9.
10.
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). doi:10.​1007/​11426639_​26 CrossRef
11.
12.
Boneh, D., Gentry, C., Hamburg, M.: Space-efficient identity based encryption without pairings. In: 48th FOCS, pp. 647–657. IEEE Computer Society Press, Providence, 20–23 October 2007
13.
Boneh, D., Papakonstantinou, P.A., Rackoff, C., Vahlis, Y., Waters, B.: On the impossibility of basing identity based encryption on trapdoor permutations. In: 49th FOCS, pp. 283–292. IEEE Computer Society Press, Philadelphia, 25–28 October 2008
14.
15.
16.
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). doi:10.​1007/​3-540-39200-9_​16 CrossRef
17.
Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 523–552. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-13190-5_​27 CrossRef
18.
Cho, C., Döttling, N., Garg, S., Gupta, D., Miao, P., Polychroniadou, A.: Laconic receiver oblivious transfer and its applications. In: CRYPTO (2017, to appear)
19.
Cocks, C.: An identity based encryption scheme based on quadratic residues. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 360–363. Springer, Heidelberg (2001). doi:10.​1007/​3-540-45325-3_​32 CrossRef
20.
21.
Döttling, N., Garg, S.: From selective IBE to full IBE and selective HIBE. Manuscript (2017)
22.
Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 467–476. ACM Press, Palo Alto, 1–4 June 2013
23.
Garg, S., Lu, S., Ostrovsky, R.: Black-box garbled RAM. In: Guruswami, V. (ed.) 56th FOCS, pp. 210–229. IEEE Computer Society Press, Berkeley, 17–20 October 2015
24.
Garg, S., Lu, S., Ostrovsky, R., Scafuro, A.: Garbled RAM from one-way functions. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th ACM STOC, pp. 449–458. ACM Press, Portland, 14–17 June 2015
25.
26.
Gentry, C., Halevi, S., Lu, S., Ostrovsky, R., Raykova, M., Wichs, D.: Garbled RAM revisited. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 405–422. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-55220-5_​23 CrossRef
27.
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197–206. ACM Press, Victoria, 17–20 May 2008
28.
29.
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions (extended abstract). In: 25th FOCS, pp. 464–479. IEEE Computer Society Press, Singer Island, 24–26 October 1984
30.
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: 21st ACM STOC, pp. 25–32. ACM Press, Seattle, 15–17 May 1989
31.
32.
33.
34.
35.
Lewko, A., Waters, B.: New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 455–479. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-11799-2_​27 CrossRef
36.
Lindell, Y., Pinkas, B.: A proof of security of Yao’s protocol for two-party computation. J. Cryptol. 22(2), 161–188 (2009)MathSciNetCrossRefMATH
37.
38.
39.
Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986). doi:10.​1007/​3-540-39799-X_​31
40.
Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: 21st ACM STOC, pp. 33–43. ACM Press, Seattle, 15–17 May 1989
41.
Okamoto, T., Takashima, K.: Fully secure functional encryption with general relations from the decisional linear assumption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 191–208. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14623-7_​11 CrossRef
42.
43.
Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signature and public-key cryptosystems. Commun. Assoc. Comput. Mach. 21(2), 120–126 (1978)MathSciNetMATH
44.
45.
Shi, E., Waters, B.: Delegating capabilities in predicate encryption systems. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 560–578. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-70583-3_​46 CrossRef
46.
Shmuely, Z.: Composite Diffie-hellman public-key generating systems are hard to break. Technical report no. 356, Computer Science Department, Technion, Israel (1985)
47.
48.
Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005). doi:10.​1007/​11426639_​7 CrossRef
49.
Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: 23rd FOCS, pp. 160–164. IEEE Computer Society Press, Chicago, 3–5 November 1982
Metadaten
Titel
Identity-Based Encryption from the Diffie-Hellman Assumption
verfasst von
Nico Döttling
Sanjam Garg
Copyright-Jahr
2017
Buch
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63687-0

Electronic ISBN: 978-3-319-63688-7

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-63688-7_18

Premium Partner

    Bildnachweise