Top

Published in:

2017 | OriginalPaper | Chapter

Identity-Based Encryption from the Diffie-Hellman Assumption

Authors : Nico Döttling, Sanjam Garg

Published in: Advances in Cryptology – CRYPTO 2017

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Watermarking Cryptographic Functionalities from Standard Lattice Assumptions

next chapter The First Collision for Full SHA-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.

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].

In Sect. 5, we explain our constructions of chameleon encryption based on the (Computational) Diffie-Hellman Assumption, or the Factoring Assumption.

We use \(\epsilon \) to denote the empty string.

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].

For this part of the intuition, we assume familiarity with garbled circuits.

We use this notion only when the sampling can be done by a PPT algorithm and the sampling algorithm is implicit.

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.

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}\).

\(\mathsf {ct}\) is assumed to contain \((\mathsf {h},i,b)\).

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.

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.

We also implicitly include the public and secret parameters for the group \(\mathbb {G}\) in \(\mathsf {k}\) and \(\mathsf {t}\) respectively.

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.

A prime number \(P > 2\) is called safe prime if \((P-1)/2\) is also prime.

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}\).

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.

Random coins used by these circuits are hardwired in them. For simplicity, we do not mention them explicitly.

\(\mathsf {F}(s,\varepsilon )\) is set to output s.

The trapdoor for the global hash function is not needed in the construction or the proof and is therefore dropped.

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}}\).

For \(i < n\), \(z_\mathsf {v}\) will become the \(x_\mathsf {v}\) in next iteration.

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}^*\).

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.

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}\).

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). doi:10.1007/978-3-642-13190-5_28 CrossRef

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

Agrawal, S., Boyen, X.: Identity-based encryption from lattices in the standard model. Manuscript (2009)

Ananth, P., Boneh, D., Garg, S., Sahai, A., Zhandry, M.: Differing-inputs obfuscation and applications. Cryptology ePrint Archive, Report 2013/689 (2013). http://eprint.iacr.org/2013/689

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

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

Biham, E., Boneh, D., Reingold, O.: Generalized Diffie-Hellman modulo a composite is not weaker than factoring. Cryptology ePrint Archive, Report 1997/014 (1997). http://eprint.iacr.org/1997/014

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

Boneh, D., Boyen, X.: Secure identity based encryption without random oracles. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 443–459. Springer, Heidelberg (2004). doi:10.1007/978-3-540-28628-8_27 CrossRef

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.

Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001). doi:10.1007/3-540-44647-8_13 CrossRef

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.

Boyle, E., Chung, K.-M., Pass, R.: On extractability obfuscation. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 52–73. Springer, Heidelberg (2014). doi:10.1007/978-3-642-54242-8_3 CrossRef

15.

Brassard, G., Chaum, D., Crépeau, C.: Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37(2), 156–189 (1988)MathSciNetCrossRefMATH

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.

Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976)MathSciNetCrossRefMATH

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.

Gentry, C., Halevi, S.: Hierarchical identity based encryption with polynomially many levels. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 437–456. Springer, Heidelberg (2009). doi:10.1007/978-3-642-00457-5_26 CrossRef

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.

Gentry, C., Silverberg, A.: Hierarchical ID-based cryptography. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 548–566. Springer, Heidelberg (2002). doi:10.1007/3-540-36178-2_34 CrossRef

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.

Hofheinz, D., Kiltz, E.: The group of signed quadratic residues and applications. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 637–653. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03356-8_37 CrossRef

32.

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). doi:10.1007/3-540-46035-7_31 CrossRef

33.

Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48(177), 203–209 (1987)MathSciNetCrossRefMATH

34.

Krawczyk, H., Rabin, T.: Chameleon hashing and signatures. Cryptology ePrint Archive, Report 1998/010 (1998). http://eprint.iacr.org/1998/010

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.

Lu, S., Ostrovsky, R.: How to garble RAM programs? In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 719–734. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38348-9_42 CrossRef

38.

McCurley, K.S.: A key distribution system equivalent to factoring. J. Cryptol. 1(2), 95–105 (1988)MathSciNetCrossRefMATH

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.

Papakonstantinou, P.A., Rackoff, C.W., Vahlis, Y.: How powerful are the DDH hard groups? Cryptology ePrint Archive, Report 2012/653 (2012). http://eprint.iacr.org/2012/653

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.

Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985). doi:10.1007/3-540-39568-7_5 CrossRef

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.

Waters, B.: Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 619–636. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03356-8_36 CrossRef

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

Title: Identity-Based Encryption from the Diffie-Hellman Assumption
Authors: Nico Döttling
Sanjam Garg
Publisher: Springer International Publishing
Book: Advances in Cryptology – CRYPTO 2017
Print ISBN: 978-3-319-63687-0

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

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

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner