nach oben

International Journal of Information Security

Erschienen in:

01.02.2014 | Regular Contribution

Plaintext awareness in identity-based key encapsulation

verfasst von: Mark Manulis, Bertram Poettering, Douglas Stebila

Erschienen in: International Journal of Information Security | Ausgabe 1/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The notion of plaintext awareness (\({\mathsf{PA}}\)) has many applications in public key cryptography: it offers unique, stand-alone security guarantees for public key encryption schemes, has been used as a sufficient condition for proving indistinguishability against adaptive chosen-ciphertext attacks (\({\mathsf{IND}\hbox {-}{\mathsf{CCA}}}\)), and can be used to construct privacy-preserving protocols such as deniable authentication. Unlike many other security notions, plaintext awareness is very fragile when it comes to differences between the random oracle and standard models; for example, many implications involving \({\mathsf{PA}}\) in the random oracle model are not valid in the standard model and vice versa. Similarly, strategies for proving \({\mathsf{PA}}\) of schemes in one model cannot be adapted to the other model. Existing research addresses \({\mathsf{PA}}\) in detail only in the public key setting. This paper gives the first formal exploration of plaintext awareness in the identity-based setting and, as initial work, proceeds in the random oracle model. The focus is laid mainly on identity-based key encapsulation mechanisms (IB-KEMs), for which the paper presents the first definitions of plaintext awareness, highlights the role of \({\mathsf{PA}}\) in proof strategies of \({\mathsf{IND}\hbox {-}{\mathsf{CCA}}}\) security, and explores relationships between \({\mathsf{PA}}\) and other security properties. On the practical side, our work offers the first, highly efficient, general approach for building IB-KEMs that are simultaneously plaintext-aware and \({\mathsf{IND}\hbox {-}{\mathsf{CCA}}}\)-secure. Our construction is inspired by the Fujisaki-Okamoto (FO) transform, but demands weaker and more natural properties of its building blocks. This result comes from a new look at the notion of \(\gamma \)-uniformity that was inherent in the original FO transform. We show that for IB-KEMs (and PK-KEMs), this assumption can be replaced with a weaker computational notion, which is in fact implied by one-wayness. Finally, we give the first concrete IB-KEM scheme that is \({\mathsf{PA}}\) and \({\mathsf{IND}\hbox {-}{\mathsf{CCA}}}\)-secure by applying our construction to a popular IB-KEM and optimizing it for better performance.

Vorheriger Artikel A formalization of card-based cryptographic protocols via abstract machine

Nächster Artikel Group signature implies public-key encryption with non-interactive opening

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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+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 "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

Nur mit Berechtigung zugänglich

By \({\mathsf{CCA}}\) in this paper, we mean adaptive chosen-ciphertext attacks, often referred to \({\mathsf{CCA2}}\).

Alternative definitions of plaintext awareness in the standard model were earlier proposed by Herzog et al. [30]. They consider a specialized PKE setting where both senders and receivers generate individual secret/public key pairs and register their public keys with a trusted authority. In contrast, definitions from [3‐5] are more standard in that they do not rely on registration authorities and assume that only recipients have public keys.

Strictly speaking, naming a KEM’s property “plaintext awareness” can be misleading: KEMs do not process messages in the classical sense, but only keys. Although one could argue that key awareness would be a better name for the intended property, in this paper we stick to “plaintext awareness” that has been around in the context of PKE for the last two decades.

Consider, for a justification, the following example (see also Lemma 13 for a more detailed discussion). Given an IB-KEM \(\varPi \), derive from it IB-KEM \(\varPi '\) such that \({\mathsf{Setup}}'\equiv {\mathsf{Setup}},\,{\mathsf{Extract}}'\equiv {\mathsf{Extract}}, \,{\mathsf{Encap}}'_{mpk}(id)\equiv [(c,K)\leftarrow {\mathsf{Encap}}_{mpk}(id),K'\leftarrow H(c,K),\text {return }(c,K')], \,{\mathsf{Decap}}'_{sk}(c)\equiv [K\leftarrow {\mathsf{Decap}}_{sk}(c),\text {return }H(c,K)]\), where \(H\) is an independent random oracle. Intuitively, if \(\varPi \) is plaintext-aware then so is \(\varPi '\), as a plaintext extractor \({\mathcal {K}}\) could extract \(K\) from \(c\) and then derive \(K'\leftarrow H(c,K)\). This reasoning, however, assumes that \({\mathcal {K}}\) has access to random oracle \(H\).

More precisely, the schemes presented in [11, 38] are not IB-KEMs, but rather IBE schemes. In this paper we consider the IB-KEMs that underlie their (hybrid) constructions.

On first sight it seems that by applying the \(H'\) hash function to intermediate key \(\overline{K}\) we lose a factor of \(q_{H'}\) in the security reduction. However, Remark 9 shows that this is not true: as \(H'(\overline{K})\) is an \(\mathsf{IND}\)-secure key, we correspondingly get tighter security for the \(\mathcal {F}\) construction.

A plaintext creator is necessary when considering encryption instead of a KEM.

Abe, M., Gennaro, R., Kurosawa, K., Shoup, V.: Tag-KEM/DEM: a new framework for hybrid encryption and a new analysis of Kurosawa-Desmedt KEM. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 128–146. Springer, Berlin (2005)

Aranha, D.F., Karabina, K., Longa, P., Gebotys, C.H., López, J.: Faster explicit formulas for computing pairings over ordinary curves. In: Paterson, K. (ed.) 30th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2011). LNCS, vol. 6632, pp. 48–68. Springer, (2010)

Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO’98. LNCS, vol. 1462, pp. 26–45. Springer, Berlin (1998)

Bellare, M., Palacio, A.: Towards plaintext-aware public-key encryption without random oracles. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 37–52. Springer, Berlin (2004), full version available as http://cseweb.ucsd.edu/users/mihir/papers/pa.pdf

Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: Santis, A.D. (ed.) EUROCRYPT’94. LNCS, vol. 950, pp. 92–111. Springer, Berlin (1994), full version available as http://www-cse.ucsd.edu/mihir/papers/oaep.html

Bentahar, K., Farshim, P., Malone-Lee, J., Smart, N.P.: Generic constructions of identity-based and certificateless KEMs. J. Cryptol. 21(2), 178–199 (2008)CrossRefMATHMathSciNet

Birkett, J., Dent, A.W.: Relations among notions of plaintext awareness. In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 47–64. Springer, Berlin (2008)

Birkett, J., Dent, A.W.: Security models and proof strategies for plaintext-aware encryption. Manuscript. http://www.isg.rhul.ac.uk/alex/papers/plaintext_journal.pdf (2011)

Blake, I., Seroussi, G., Smart, N., Cassels, J.W.S.: Advances in Elliptic Curve Cryptography (London Mathematical Society Lecture Note Series). Cambridge University Press, New York (2005)CrossRef

10.

Boneh, D., Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. SIAM J. Comput. 36(5), 1301–1328 (2007)CrossRefMathSciNet

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, Berlin (2001)

12.

Boneh, D., Katz, J.: Improved efficiency for CCA-secure cryptosystems built using identity-based encryption. In: Menezes, A.J. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 87–103. Springer, Berlin (2005)

13.

Boyen, X., Mei, Q., Waters, B.: Direct chosen ciphertext security from identity-based techniques. In: ACM CCS 2005. pp. 320–329. ACM (2005)

14.

Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 207–222. Springer, Berlin (2004)

15.

Chen, L., Cheng, Z.: Security proof of Sakai-Kasahara’s identity-based encryption scheme. In: Smart, N.P. (ed.) Cryptography and Coding—10th IMA International Conference. LNCS, vol. 3796, pp. 442–459. Springer, Berlin (2005)

16.

Chen, L., Cheng, Z., Malone-Lee, J., Smart, N.P.: Efficient ID-KEM based on the Sakai–Kasahara key construction. IEE Proceedings-Information Security 153(1), 19–26 (2006, March), http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1613725&isnumber=33872

17.

Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Berlin (2002)

18.

Cramer, R., Shoup, V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33(1), 167–226 (2003)CrossRefMATHMathSciNet

19.

Dent, A.W.: A designer’s guide to KEMs. In: Paterson, K.G. (ed.) Cryptography and Coding. LNCS, vol. 2898, pp. 133–151. Springer, Berlin (2003), updated version available at http://eprint.iacr.org/2002/174

20.

Dent, A.W.: The Cramer-Shoup encryption scheme is plaintext aware in the standard model. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 289–307. Springer, Berlin (2006)

21.

Desmedt, Y., Gennaro, R., Kurosawa, K., Shoup, V.: A new and improved paradigm for hybrid encryption secure against chosen-ciphertext attack. J. Cryptol. 23(1), 91–120 (2010)CrossRefMATHMathSciNet

22.

Di Raimondo, M., Gennaro, R., Krawczyk, H.: Deniable authentication and key exchange. In: Wright, R., De Capitani de Vimercati, S., Shmatikov, V. (eds.) ACM CCS 2006. pp. 400–409. ACM (2006), full version available as http://eprint.iacr.org/2006/280

23.

Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM J. Comput. 30(2), 391–437 (2000)CrossRefMATHMathSciNet

24.

ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO. Lecture Notes in Computer Science, vol. 196, pp. 10–18. Springer, Berlin (1984)

25.

Elkind, E., Sahai, A.: A Unified Methodology For Constructing Public-Key Encryption Schemes Secure Against Adaptive Chosen-Ciphertext Attack. Cryptology ePrint Archive, Report 2002/042 (2002), http://eprint.iacr.org/

26.

Fujisaki, E., Okamoto, T.: How to enhance the security of public-key encryption at minimum cost. In: Imai, H., Zheng, Y. (eds.) PKC 1999. LNCS, vol. 1560, pp. 53–68. Springer, Belin (1999)

27.

Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO’99. LNCS, vol. 1666, pp. 537–554. Springer, Berlin (1999)

28.

Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Discrete Appl. Math. 156(16), 3113–3121 (2008)CrossRefMATHMathSciNet

29.

Herranz, J., Hofheinz, D., Kiltz, E.: Some (in)sufficient conditions for secure hybrid encryption. Inf. Comput. 208(11), 1243–1257 (2010)CrossRefMATHMathSciNet

30.

Herzog, J., Liskov, M., Micali, S.: Plaintext awareness via key registration. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 548–564. Springer, Berlin (2003)

31.

Jiang, S., Wang, H.: Plaintext-awareness of hybrid encryption. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 57–72. Springer, Berlin (2010), full version available at http://sites.google.com/site/shaoquan0825/DHIES-8.pdf

32.

Kiltz, E.: Chosen-ciphertext security from tag-based encryption. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 581–600. Springer, Berlin (2006)

33.

Kiltz, E., Galindo, D.: Direct chosen-ciphertext secure identity-based key encapsulation without random oracles. Theor. Comput. Sci. 410(47–49), 5093–5111 (2009)

34.

Kitagawa, T., Yang, P., Hanaoka, G., Zhang, R., Watanabe, H., Matsuura, K., Imai, H.: Generic transforms to acquire CCA-security for identity based encryption: the cases of FOpkc and REACT. In: Batten, L.M., Safavi-Naini, R. (eds.) ACISP 2006. LNCS, vol. 4058, pp. 348–359. Springer, Berlin (2006)

35.

Kurosawa, K., Desmedt, Y.: A new paradigm of hybrid encryption scheme. In: Franklin, M. (ed.) CRYPTO. LNCS, vol. 3152, pp. 426–442. Springer, Berlin (2004)

36.

Okamoto, T., Pointcheval, D.: REACT: rapid enhanced-security asymmetric cryptosystem transform. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 159–175. Springer, Berlin (2001). vol.

37.

Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: FOCS 1999. pp. 543–553 (1999)

38.

Sakai, R., Kasahara, M.: ID based cryptosystems with pairing on elliptic curve. Cryptology ePrint archive, report 2003/054 (2003) http://eprint.iacr.org/

39.

Shoup, V.: Using hash functions as a hedge against chosen ciphertext attack. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 275–288. Springer, Berlin (2000)

40.

Teranishi, I., Ogata, W.: Relationship between standard model plaintext awareness and message hiding. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 226–240. Springer, Berlin (2006)

41.

Teranishi, I., Ogata, W.: Cramer-shoup satisfies a stronger plaintext awareness under a weaker assumption. In: Ostrovsky, R., Prisco, R.D., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 109–125. Springer, Berlin (2008)

42.

Yang, P., Kitagawa, T., Hanaoka, G., Zhang, R., Matsuura, K., Imai, H.: Applying Fujisaki-Okamoto to identity-based encryption. In: Fossorier, M.P., Imai, H., Lin, S., Poli, A. (eds.) AAECC-16 2006. LNCS, vol. 3857, pp. 183–192 (2006)

Titel: Plaintext awareness in identity-based key encapsulation
verfasst von: Mark Manulis
Bertram Poettering
Douglas Stebila
Publikationsdatum: 01.02.2014
Verlag: Springer Berlin Heidelberg
Erschienen in: International Journal of Information Security / Ausgabe 1/2014
Print ISSN: 1615-5262
Elektronische ISSN: 1615-5270
DOI: https://doi.org/10.1007/s10207-013-0218-5

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 "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2014

Group signature implies public-key encryption with non-interactive opening

Perceptual hash function for scalable video

RORI-based countermeasure selection using the OrBAC formalism

A formalization of card-based cryptographic protocols via abstract machine

Portfolio optimization of computer and mobile botnets

Premium Partner