zbMATH — the first resource for mathematics

Tag-KEM/DEM: A new framework for hybrid encryption. (English) Zbl 1147.68498
Summary: This paper presents a novel framework for the generic construction of hybrid encryption schemes which produces more efficient schemes than the ones known before. A previous framework introduced by Shoup combines a Key Encapsulation Mechanism (KEM) and a Data Encryption Mechanism (DEM). While it is sufficient to require both components to be secure against Chosen Ciphertext Attacks (CCA-secure), Kurosawa and Desmedt showed a particular example of KEM that is not CCA-secure but can be securely combined with a specific type of CCA-secure DEM to obtain a more efficient, CCA-secure hybrid encryption scheme. There are also many other efficient hybrid encryption schemes in the literature that do not fit into Shoup’s framework. These facts serve as motivation to seek another framework.
The framework we propose yields more efficient hybrid scheme, and in addition provides insightful explanation about existing schemes that do not fit into the previous framework. Moreover, it allows immediate conversion from a class of threshold public-key encryption to a threshold hybrid one without considerable overhead, which may not be possible in the previous approach.

68P25 Data encryption (aspects in computer science)
Full Text: DOI
[1] Abe, M.; Wiener, M., Robust distributed multiplication without interaction, Advances in Cryptology—CRYPTO’99, 130-147 (1999), Berlin: Springer, Berlin · Zbl 0940.94005
[2] M. Abe, S. Fehr, Adaptively secure Feldman VSS and applications to universally-composable threshold cryptography. IACR ePrint Archive 2004/119, June 10 2004. Preliminary version was presented in CRYPTO 2004 · Zbl 1104.94042
[3] Abe, M.; Gennaro, R.; Kurosawa, K.; Shoup, V.; Cramer, R., Tag-KEM/DEM: a new framework for hybrid encryption and a new analysis of Kurosawa-Desmedt KEM, Advances in Cryptology—EUROCRYPT 2005, 128-146 (2005), Berlin: Springer, Berlin · Zbl 1137.94336
[4] M. Bellare, P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in First ACM Conference on Computer and Communication Security (Association for Computing Machinery, 1993), pp. 62-73
[5] M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in Proceedings of the 20th Annual ACM Symposium on the Theory of Computing, pp. 1-10, 1988
[6] K. Bentahar, P. Farshim, M. Malone-Lee, N. Smart, Generic constructions of identity-based and certificateless KEMs. IACR e-print Archive 058/2005, 2005 · Zbl 1143.94340
[7] Bleichenbacher, D.; Krawczyk, H., Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1, Advances in Cryptology—CRYPTO’98, 1-12 (1998), Berlin: Springer, Berlin · Zbl 0931.94017
[8] Boneh, D.; Killian, J., Simplified OAEP for the RSA and Rabin functions, Advances in Cryptology—CRYPTO 2001, 275-291 (2001), Berlin: Springer, Berlin · Zbl 1002.94526
[9] Boneh, D.; Boyen, X., Efficient selective-ID secure identity based encryption, Advances in Cryptology—EUROCRYPT 2004, 223-238 (2004), Berlin: Springer, Berlin · Zbl 1122.94355
[10] D. Boneh, J. Katz, Improved efficiency for CCA-secure cryptosystems built using identity-based encryption. Technical Report 2004/261, IACR ePrint archive, 2004 · Zbl 1079.94535
[11] X. Boyen, Q. Mei, B. Waters, Direct chosen ciphertext security from identity-based techniques, in ACM Conference on Computer and Communications Security (ACM, 2005), pp. 320-329. Also available at IACR e-print 2005/288
[12] Boneh, D.; Boyen, X.; Halevi, S.; Rabin, T.; Halevi, S., Chosen ciphertext secure public key threshold encryption without random oracles, Topics in Cryptology—CT-RSA 2006, 226-243 (2006), Berlin: Springer, Berlin · Zbl 1125.94012
[13] Canetti, R.; Goldwasser, S.; Stern, J., An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack, Advances in Cryptology—EUROCRYPT’99, 90-106 (1999), Berlin: Springer, Berlin · Zbl 0948.94008
[14] Canetti, R.; Krawczyk, H.; Nielsen, J.; Boneh, D., Relaxing chosen-ciphertext security, Advances in Cryptology—CRYPTO 2003, 565-582 (2003), Berlin: Springer, Berlin · Zbl 1122.94359
[15] Canetti, R.; Halevi, S.; Katz, J., Chosen-ciphertext security from identity-based encryption, Advances in Cryptology—EUROCRYPT 2004, 207-222 (2004), Berlin: Springer, Berlin · Zbl 1122.94358
[16] Cramer, R.; Shoup, V.; Krawczyk, H., A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, Advances in Cryptology—CRYPTO’98, 13-25 (1998), Berlin: Springer, Berlin · Zbl 0931.94018
[17] Cramer, R.; Shoup, V.; Knudsen, L., Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, Advances in Cryptology—EUROCRYPTO 2002, 45-64 (2002), Berlin: Springer, Berlin · Zbl 1055.94011
[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) · Zbl 1045.94013
[19] Dent, A.; Paterson, K. G., A designer’s guide to KEMs, 9th IMA International Conference on Cryptography and Coding, 133-151 (2003), Berlin: Springer, Berlin · Zbl 1123.94336
[20] Desmedt, Y. G.; Frankel, Y.; Brassard, G., Threshold cryptosystems, Advances in Cryptology—CRYPTO’89, 307-315 (1990), Berlin: Springer, Berlin
[21] Dolev, D.; Dwork, C.; Naor, M., Nonmalleable cryptography, SIAM J. Comput., 30, 2, 391-437 (2000) · Zbl 0963.68067
[22] Fujisaki, E.; Okamoto, T.; Wiener, M., Secure integration of asymmetric and symmetric encryption schemes, Advances in Cryptology—CRYPTO’99, 537-554 (1999), Berlin: Springer, Berlin · Zbl 0942.94019
[23] R. Gennaro, V. Shoup, A note on an encryption scheme of Kurosawa and Desmedt. Technical Report 2004/194, IACR ePrint archive, 2004
[24] Gentry, C.; Franklin, M., How to compress Rabin ciphertexts and signatures (and more), Advances in Cryptology—CRYPTO 2004, 179-200 (2004), Berlin: Springer, Berlin · Zbl 1104.68045
[25] O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in Proceedings of the 19th annual ACM Symposium on the Theory of Computing, New York City, pp. 218-229, 1987
[26] J. Herranz, D. Hofheinz, E. Kiltz, The Kurosawa-Desmedt key encapsulation is not chosen-ciphertext secure. IACR e-print Archive 2006/207, 2005 · Zbl 1200.94042
[27] Jarecki, S.; Lysyanskaya, A., Adaptively secure threshold cryptography: introducing concurrency, removing erasures (extended abstract), Advances in Cryptology—EUROCRYPT 2000, 221-242 (2000), Berlin: Springer, Berlin · Zbl 1082.94522
[28] Kiltz, E.; Halevi, S.; Rabin, T., Chosen-ciphertext security from tag-based encryption, Theory of Cryptography—TCC’06, 581-600 (2006), Berlin: Springer, Berlin · Zbl 1113.94008
[29] Kurosawa, K.; Desmedt, Y.; Franklin, M., A new paradigm of hybrid encryption scheme, Advances in Cryptology—CRYPTO 2004, 426-442 (2004), Berlin: Springer, Berlin · Zbl 1104.94028
[30] MacKenzie, P.; Reiter, M. K.; Yang, K.; Naor, M., Alternatives to non-malleability: definitions, constructions, and applications, Theory of Cryptography—TCC’04, 171-190 (2004), Berlin: Springer, Berlin · Zbl 1197.94193
[31] Nagao, W.; Manabe, Y.; Okamoto, T., A universally composable secure channel based on the KEM-DEM framework, Theory of Cryptography—TCC’05, 426-444 (2005), Berlin: Springer, Berlin · Zbl 1079.94567
[32] M. Naor, M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks. In Proceedings of the 22nd annual ACM Symposium on the Theory of Computing, pp. 427-437, 1990
[33] Okamoto, T.; Pointcheval, D., REACT: Rapid enhanced-security asymmetric cryptosystem transform, RSA’2001 (2001), Berlin: Springer, Berlin · Zbl 0991.94046
[34] Rackoff, C.; Simon, D., Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack, Advances in Cryptology—CRYPTO’91, 433-444 (1992), Berlin: Springer, Berlin · Zbl 0767.94006
[35] Shoup, V., Using hash functions as a hedge against chosen ciphertext attack, Advances in Cryptology—EUROCRYPT 2000, 275-288 (2000), Berlin: Springer, Berlin · Zbl 1082.94530
[36] Shoup, V., OAEP reconsidered, Advances in Cryptology—CRYPTO 2001, 239-259 (2001), Berlin: Springer, Berlin · Zbl 1002.94519
[37] V. Shoup, ISO 18033-2: An emerging standard for public-key encryption (committee draft). Available at http://shoup.net/iso/, June 3 2004
[38] Shoup, V.; Gennaro, R., Securing threshold cryptosystems against chosen ciphertext attack, J. Cryptol., 15, 2, 75-96 (2002) · Zbl 0997.94016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.