Article

Chosen-Ciphertext security from tag-based encryption

Author:

Eike KiltzAuthors Info & Claims

TCC'06: Proceedings of the Third conference on Theory of Cryptography

Pages 581 - 600

https://doi.org/10.1007/11681878_30

Published: 04 March 2006 Publication History

Abstract

One of the celebrated applications of Identity-Based Encryption (IBE) is the Canetti, Halevi, and Katz (CHK) transformation from any (selective-identity secure) IBE scheme into a full chosen-ciphertext secure encryption scheme. Since such IBE schemes in the standard model are known from previous work this immediately provides new chosenciphertext secure encryption schemes in the standard model.

This paper revisits the notion of Tag-Based Encryption (TBE) and provides security definitions for the selective-tag case. Even though TBE schemes belong to a more general class of cryptographic schemes than IBE, we observe that (selective-tag secure) TBE is a su.cient primitive for the CHK transformation and therefore implies chosen-ciphertext secure encryption.

We construct efficient and practical TBE schemes and give tight security reductions in the standard model from the Decisional Linear Assumption in gap-groups. In contrast to all known IBE schemes our TBE construction does not directly deploy pairings. Instantiating the CHK transformation with our TBE scheme results in an encryption scheme whose decryption can be carried out in one single multi-exponentiation.

Furthermore, we show how to apply the techniques gained from the TBE construction to directly design a new Key Encapsulation Mechanism. Since in this case we can avoid the CHK transformation the scheme results in improved efficiency.

References

[1]

M. Abe, R. Gennaro, K. Kurosawa, and V. Shoup. Tag-KEM/DEM: A new framework for hybrid encryption and a new analysis of Kurosawa-Desmedt KEM. In R. Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 128-146. Springer-Verlag, May 2005.

Digital Library

[2]

M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In ACM CCS 93, pages 62-73. ACM Press, Nov. 1993.

Digital Library

[3]

D. Boneh and X. Boyen. Efficient selective-id secure identity based encryption without random oracles. In C. Cachin and J. Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 223-238. Springer-Verlag, May 2004.

[4]

D. Boneh, X. Boyen, and H. Shacham. Short group signatures. In M. Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 41-55. Springer-Verlag, Aug. 2004.

[5]

D. Boneh, R. Canetti, S. Halevi, and J. Katz. Chosen-ciphertext security from identity-based encryption. Journal submission. Available from author's web page http://crypto.stanford.edu/~dabo/pubs.html, November 2005.

Digital Library

[6]

D. Boneh and M. K. Franklin. Identity based encryption from the Weil pairing. SIAM Journal on Computing, 32(3):586-615, 2003.

Digital Library

[7]

D. Boneh and J. Katz. Improved efficiency for CCA-secure cryptosystems built using identity-based encryption. In A. Menezes, editor, CT-RSA 2005, volume 3376 of LNCS, pages 87-103. Springer-Verlag, Feb. 2005.

Digital Library

[8]

D. Boneh and H. Shacham. Group signatures with verifier-local revocation. In ACM CCS 04, pages 168-177. ACM Press, Oct. 2004.

Digital Library

[9]

X. Boyen, Q. Mei, and B. Waters. Simple and efficient CCA2 security from IBE techniques. In ACM Conference on Computer and Communications Security--CCS 2005, pages 320-329. New-York: ACM Press, 2005.

Digital Library

[10]

R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. In 30th ACM STOC, pages 209-218. ACM Press, May 1998.

Digital Library

[11]

R. Canetti, S. Halevi, and J. Katz. Chosen-ciphertext security from identity-based encryption. In C. Cachin and J. Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 207-222. Springer-Verlag, May 2004.

[12]

R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In H. Krawczyk, editor, CRYPTO'98, volume 1462 of LNCS, pages 13-25. Springer-Verlag, Aug. 1998.

Digital Library

[13]

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

Digital Library

[14]

W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22:644-654, 1978.

Digital Library

[15]

D. Dolev, C. Dwork, and M. Naor. Nonmalleable cryptography. SIAM Journal on Computing, 30(2):391-437, 2000.

Digital Library

[16]

T. El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In G. R. Blakley and D. Chaum, editors, CRYPTO'84, volume 196 of LNCS, pages 10-18. Springer-Verlag, Aug. 1985.

Digital Library

[17]

E. Elkind and A. Sahai. 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/.

[18]

D. Galindo and I. Hasuo. Security notions for identity based encryption. Cryptology ePrint Archive, Report 2005/253, 2005. http://eprint.iacr.org/.

[19]

S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28:270-299, 1984.

[20]

E. Kiltz. Chosen-ciphertext security from tag-based encryption. Cryptology ePrint Archive, 2005. http://eprint.iacr.org/.

[21]

K. Kurosawa and Y. Desmedt. A new paradigm of hybrid encryption scheme. In M. Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 426-442. Springer-Verlag, Aug. 2004.

[22]

P. D. MacKenzie, M. K. Reiter, and K. Yang. Alternatives to non-malleability: Definitions, constructions, and applications. In M. Naor, editor, TCC 2004, volume 2951 of LNCS, pages 171-190. Springer-Verlag, Feb. 2004.

[23]

M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In 22nd ACM STOC. ACM Press, May 1990.

Digital Library

[24]

L. Nguyen and R. Safavi-Naini. Efficient and provably secure trapdoor-free group signature schemes from bilinear pairings. In P. J. Lee, editor, ASIACRYPT 2004, volume 3329 of LNCS, pages 372-386. Springer-Verlag, Dec. 2004.

[25]

T. Okamoto and D. Pointcheval. The gap-problems: A new class of problems for the security of cryptographic schemes. In K. Kim, editor, PKC 2001, volume 1992 of LNCS, pages 104-118. Springer-Verlag, Feb. 2001.

Digital Library

[26]

C. Rackoff and D. R. Simon. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In J. Feigenbaum, editor, CRYPTO'91, volume 576 of LNCS, pages 433-444. Springer-Verlag, Aug. 1991.

Digital Library

[27]

R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signature and public-key cryptosystems. Communications of the ACM, 21(2):120- 126, 1978.

Digital Library

[28]

M. Scott. Faster pairings using an elliptic curve with an efficient endomorphism. Cryptology ePrint Archive, Report 2005/252, 2005. http://eprint.iacr.org/.

[29]

V. Shoup. A proposal for an ISO standard for public key encryption (version 2.1). manuscript, 2001. Available on http://shoup.net/papers/.

[30]

B. R. Waters. Efficient identity-based encryption without random oracles. In R. Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 114-127. Springer-Verlag, May 2005.

Digital Library

Cited By

Devillez HPereira OPeters T(2022)Traceable Receipt-Free EncryptionAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22969-5_10(273-303)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-22969-5_10
Nguyen KGuo FSusilo WYang G(2022)Multimodal Private SignaturesAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15979-4_27(792-822)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15979-4_27
Heseri NNuida K(2022)Computational Irrelevancy: Bridging the Gap Between Pseudo- and Real Randomness in MPC ProtocolsAdvances in Information and Computer Security10.1007/978-3-031-15255-9_11(208-223)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15255-9_11
Show More Cited By

Index Terms

Chosen-Ciphertext security from tag-based encryption

Recommendations

Chosen ciphertext security from identity-based encryption without strong condition
IWSEC'06: Proceedings of the 1st international conference on Security

Recently, Canetti et al [11] gave a generic construction (called CHK construction) of public key encryption (PKE) from a selective identity-based encryption scheme combined with a strong one-time signature scheme. Later, few schemes were proposed to ...
Chosen-Ciphertext Security from Identity-Based Encryption

We propose simple and efficient CCA-secure public-key encryption schemes (i.e., schemes secure against adaptive chosen-ciphertext attacks) based on any identity-based encryption (IBE) scheme. Our constructions have ramifications of both theoretical and ...
Selectively chosen ciphertext security in threshold public-key encryption

Threshold public-key encryption can control decryption abilities of an authorized user group in such a way that each user of the group can produce only a decryption share and at least t of them should collect decryption shares to recover a message. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

TCC'06: Proceedings of the Third conference on Theory of Cryptography

March 2006

616 pages

ISBN:3540327312

Editors:
Shai Halevi
IBM Research, Hawthorne, NY
,
Tal Rabin
IBM T.J.Watson Research Center, Hawthorne, NY

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 04 March 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

127
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Devillez HPereira OPeters T(2022)Traceable Receipt-Free EncryptionAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22969-5_10(273-303)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-22969-5_10
Nguyen KGuo FSusilo WYang G(2022)Multimodal Private SignaturesAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15979-4_27(792-822)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15979-4_27
Heseri NNuida K(2022)Computational Irrelevancy: Bridging the Gap Between Pseudo- and Real Randomness in MPC ProtocolsAdvances in Information and Computer Security10.1007/978-3-031-15255-9_11(208-223)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15255-9_11
Libert BNguyen KPeters TYung M(2022)One-Shot Fiat-Shamir-Based NIZK Arguments of Composite Residuosity and Logarithmic-Size Ring Signatures in the Standard ModelAdvances in Cryptology – EUROCRYPT 202210.1007/978-3-031-07085-3_17(488-519)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-07085-3_17
Beskorovajnov WGröll RMüller-Quade JOttenhues ASchwerdt R(2022)A New Security Notion for PKC in the Standard Model: Weaker, Simpler, and Still Realizing Secure ChannelsPublic-Key Cryptography – PKC 202210.1007/978-3-030-97131-1_11(316-344)Online publication date: 8-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-030-97131-1_11
Beck GLen JMiers IGreen MKim YKim JVigna GShi E(2021)Fuzzy Message DetectionProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484545(1507-1528)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484545
Xagawa K(2021)The Boneh-Katz Transformation, Revisited: Pseudorandom/Obliviously-Samplable PKE from Lattices and Codes and Its ApplicationSelected Areas in Cryptography10.1007/978-3-030-99277-4_3(47-67)Online publication date: 29-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-99277-4_3
Hesse JHofheinz DKohl LLangrehr R(2021)Towards Tight Adaptive Security of Non-interactive Key ExchangeTheory of Cryptography10.1007/978-3-030-90456-2_10(286-316)Online publication date: 8-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-90456-2_10
Libert BNguyen KPeters TYung M(2021)Bifurcated Signatures: Folding the Accountability vs. Anonymity Dilemma into a Single Private Signing SchemeAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77883-5_18(521-552)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-77883-5_18
Devevey JLibert BNguyen KPeters TYung M(2021)Non-interactive CCA2-Secure Threshold Cryptosystems: Achieving Adaptive Security in the Standard Model Without PairingsPublic-Key Cryptography – PKC 202110.1007/978-3-030-75245-3_24(659-690)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-75245-3_24
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents