Article

REACT: Rapid Enhanced-Security Asymmetric Cryptosystem Transform

Authors:

Tatsuaki Okamoto,

David PointchevalAuthors Info & Claims

CT-RSA 2001: Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA

Pages 159 - 175

Published: 08 April 2001 Publication History

Abstract

Seven years after the optimal asymmetric encryption padding (OAEP) which makes chosen-ciphertext secure encryption scheme from any trapdoor one-way permutation (but whose unique application is RSA), this paper presents REACT, a new conversion which applies to any weakly secure cryptosystem, in the random oracle model: it is optimal from both the computational and the security points of view. Indeed, the overload is negligible, since it just consists of two more hashings for both encryption and decryption, and the reduction is very tight. Furthermore, advantages of REACT beyond OAEP are numerous: 1. it is more general since it applies to any partially trapdoor one-way function (a.k.a. weakly secure public-key encryption scheme) and therefore provides security relative to RSA but also to the Diffie-Hellman problem or the factorization; 2. it is possible to integrate symmetric encryption (block and stream ciphers) to reach very high speed rates; 3. it provides a key distribution with session key encryption, whose overall scheme achieves chosen-ciphertext security even with weakly secure symmetric scheme.Therefore, REACT could become a new alternative to OAEP, and even reach security relative to factorization, while allowing symmetric integration.

References

[1]

M. Abdalla, M. Bellare, and P. Rogaway. DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem. Submission to IEEE P1363a. September 1998.

[2]

M. Abdalla, M. Bellare, and P. Rogaway. The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES. In RSA '2001 , LNCS. Springer-Verlag, Berlin, 2001.

[3]

M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among Notions of Security for Public-Key Encryption Schemes. In Crypto '98 , LNCS 1462, pages 26-45. Springer-Verlag, Berlin, 1998.

[4]

M. Bellare and P. Rogaway. Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols. In Proc. of the 1st CCS , pages 62-73. ACM Press, New York, 1993.

[5]

M. Bellare and P. Rogaway. Optimal Asymmetric Encryption - How to Encrypt with RSA. In Eurocrypt '94 , LNCS 950, pages 92-111. Springer-Verlag, Berlin, 1995.

[6]

M. Bellare and A. Sahai. Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization. In Crypto '99 , LNCS 1666, pages 519-536. Springer-Verlag, Berlin, 1999.

[7]

D. Bleichenbacher. A Chosen Ciphertext Attack against Protocols based on the RSA Encryption Standard PKCS #1. In Crypto '98 , LNCS 1462, pages 1-12. Springer-Verlag, Berlin, 1998.

[8]

L. Carter and M. Wegman. Universal Hash Functions. Journal of Computer and System Sciences , 18:143-154, 1979.

[9]

D. Coppersmith, S. Halevi, and C. S. Jutla. ISO 9796 and the New Forgery Strategy. Working Draft presented at the Rump Session of Crypto '99, 1999.

[10]

J.-S. Coron, D. Naccache, and J. P. Stern. On the Security of RSA Padding. In Crypto '99 , LNCS 1666, pages 1-18. Springer-Verlag, Berlin, 1999.

[11]

R. Cramer and V. Shoup. A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack. In Crypto '98 , LNCS 1462, pages 13-25. Springer-Verlag, Berlin, 1998.

[12]

W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory , IT-22(6):644-654, November 1976.

[13]

D. Dolev, C. Dwork, and M. Naor. Non-Malleable Cryptography. In Proc. of the 23rd STOC . ACM Press, New York, 1991.

[14]

T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory , IT-31(4):469- 472, July 1985.

[15]

E. Fujisaki and T. Okamoto. How to Enhance the Security of Public-Key Encryption at Minimum Cost. In PKC '99 , LNCS 1560, pages 53-68. Springer-Verlag, Berlin, 1999.

[16]

E. Fujisaki and T. Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. In Crypto '99 , LNCS 1666, pages 537-554. Springer-Verlag, Berlin, 1999.

[17]

E. Fujisaki and T. Okamoto. How to Enhance the Security of Public-Key Encryption at Minimum Cost. IEICE Transaction of Fundamentals of Electronic Communications and Computer Science , E83-A(1):24-32, January 2000.

[18]

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

[19]

J. Hoffstein, J. Pipher, and J. H. Silverman. NTRU: A Ring Based Public Key Cryptosystem. In Algorithmic Number Theory Symposium (ANTS III) , LNCS 1423, pages 267-288. Springer-Verlag, Berlin, 1998.

[20]

M. Jakobsson. A Practical Mix. In Eurocrypt '98 , LNCS 1403, pages 448-461. Springer-Verlag, Berlin, 1998.

[21]

M. Joye, J. J. Quisquater, and M. Yung. On the Power of Misbehaving Adversaries and Cryptanalysis of EPOC. In RSA '2001 , LNCS. Springer-Verlag, Berlin, 2001.

[22]

N. Koblitz. Elliptic Curve Cryptosystems. Mathematics of Computation , 48(177):203-209, January 1987.

[23]

U. M. Maurer and S. Wolf. The Diffie-Hellman Protocol. Designs, Codes, and Cryptography , 19:147-171, 2000.

[24]

R. J. McEliece. A Public-Key Cryptosystem Based on Algebraic Coding Theory. DSN progress report , 42-44:114-116, 1978. Jet Propulsion Laboratories, CALTECH.

[25]

D. Naccache and J. Stern. A New Public-Key Cryptosystem. In Eurocrypt '97 , LNCS 1233, pages 27-36. Springer-Verlag, Berlin, 1997.

[26]

D. Naccache and J. Stern. A New Cryptosystem based on Higher Residues. In Proc. of the 5th CCS , pages 59-66. ACM Press, New York, 1998.

[27]

M. Naor and M. Yung. Public-Key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In Proc. of the 22nd STOC , pages 427-437. ACM Press, New York, 1990.

[28]

T. Okamoto and D. Pointcheval. The Gap-Problems: a New Class of Problems for the Security of Cryptographic Schemes. In PKC '2001 , LNCS. Springer-Verlag, Berlin, 2001.

[29]

T. Okamoto and S. Uchiyama. A New Public Key Cryptosystem as Secure as Factoring. In Eurocrypt '98 , LNCS 1403, pages 308-318. Springer-Verlag, Berlin, 1998.

[30]

T. Okamoto, S. Uchiyama, and E. Fujisaki. EPOC: Efficient Probabilistic Public-Key Encryption. Submission to IEEE P1363a. November 1998.

[31]

P. Paillier. Public-Key Cryptosystems Based on Discrete Logarithms Residues. In Eurocrypt '99 , LNCS 1592, pages 223-238. Springer-Verlag, Berlin, 1999.

[32]

P. Paillier and D. Pointcheval. Efficient Public-Key Cryptosystems Provably Secure against Active Adversaries. In Asiacrypt '99 , LNCS 1716, pages 165-179. Springer-Verlag, Berlin, 1999.

[33]

D. Pointcheval. HD-RSA: Hybrid Dependent RSA - a New Public-Key Encryption Scheme. Submission to IEEE P1363a. October 1999.

[34]

D. Pointcheval. New Public Key Cryptosystems based on the Dependent-RSA Problems. In Eurocrypt '99 , LNCS 1592, pages 239-254. Springer-Verlag, Berlin, 1999.

[35]

D. Pointcheval. Chosen-Ciphertext Security for any One-Way Cryptosystem. In PKC '2000 , LNCS 1751, pages 129-146. Springer-Verlag, Berlin, 2000.

[36]

C. Rackoff and D. R. Simon. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In Crypto '91 , LNCS 576, pages 433-444. Springer-Verlag, Berlin, 1992.

[37]

R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM , 21(2):120-126, February 1978.

[38]

RSA Data Security, Inc. Public Key Cryptography Standards - PKCS.

[39]

C. E. Shannon. Communication Theory of Secrecy Systems. Bell System Technical Journal , 28(4):656-715, 1949.

[40]

V. Shoup and R. Gennaro. Securing Threshold Cryptosystems against Chosen Ciphertext Attack. In Eurocrypt '98 , LNCS 1403, pages 1-16. Springer-Verlag, Berlin, 1998.

[41]

Y. Tsiounis and M. Yung. On the Security of El Gamal based Encryption. In PKC '98 , LNCS. Springer-Verlag, Berlin, 1998.

[42]

D. Wagner. The Boomerang Attack. In Proc. of the 6th FSE , LNCS 1636. Springer-Verlag, Berlin, 1999.

Cited By

Gay RHofheinz DKiltz EWee H(2016)Tightly CCA-Secure Encryption Without PairingsProceedings, Part I, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966510.5555/3081770.3081771(1-27)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081770.3081771
Kitagawa FMatsuda THanaoka GTanaka K(2016)On the Key Dependent Message Security of the Fujisaki-Okamoto ConstructionsProceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 961410.1007/978-3-662-49384-7_5(99-129)Online publication date: 6-Mar-2016
https://dl.acm.org/doi/10.1007/978-3-662-49384-7_5
Matsuda THanaoka G(2016)Trading Plaintext-Awareness for Simulatability to Achieve Chosen Ciphertext SecurityProceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 961410.1007/978-3-662-49384-7_1(3-34)Online publication date: 6-Mar-2016
https://dl.acm.org/doi/10.1007/978-3-662-49384-7_1
Show More Cited By

Index Terms

REACT: Rapid Enhanced-Security Asymmetric Cryptosystem Transform

Index terms have been assigned to the content through auto-classification.

Recommendations

PQ-REACT: Post Quantum Cryptography Framework for Energy Aware Contexts
ARES '24: Proceedings of the 19th International Conference on Availability, Reliability and Security

Public key cryptography is nowadays a crucial component of global communications which are critical to our economy, security and way of life. The quantum computers are expected to be a threat and the widely used RSA, ECDSA, ECDH, and DSA cryptosystems ...
Public-Key encryption from ID-Based encryption without one-time signature
OTM'06: Proceedings of the 2006 international conference on On the Move to Meaningful Internet Systems: AWeSOMe, CAMS, COMINF, IS, KSinBIT, MIOS-CIAO, MONET - Volume Part I

Design a secure public key encryption scheme and its security proof are one of the main interests in cryptography In 2004, Canetti, Halevi and Katz [8] constructed a public key encryption (PKE) from a selective identity-based encryption scheme with a ...
Identity-based strong designated verifier signature schemes: Attacks and new construction

A strong designated verifier signature scheme makes it possible for a signer to convince a designated verifier that she has signed a message in such a way that the designated verifier cannot transfer the signature to a third party, and no third party ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CT-RSA 2001: Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA

April 2001

471 pages

ISBN:3540418989

Editor:
David Naccache

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 April 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gay RHofheinz DKiltz EWee H(2016)Tightly CCA-Secure Encryption Without PairingsProceedings, Part I, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966510.5555/3081770.3081771(1-27)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081770.3081771
Kitagawa FMatsuda THanaoka GTanaka K(2016)On the Key Dependent Message Security of the Fujisaki-Okamoto ConstructionsProceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 961410.1007/978-3-662-49384-7_5(99-129)Online publication date: 6-Mar-2016
https://dl.acm.org/doi/10.1007/978-3-662-49384-7_5
Matsuda THanaoka G(2016)Trading Plaintext-Awareness for Simulatability to Achieve Chosen Ciphertext SecurityProceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 961410.1007/978-3-662-49384-7_1(3-34)Online publication date: 6-Mar-2016
https://dl.acm.org/doi/10.1007/978-3-662-49384-7_1
Boldyreva AKim TLipton RWarinschi B(2016)Provably-Secure Remote Memory Attestation for Heap Overflow ProtectionProceedings of the 10th International Conference on Security and Cryptography for Networks - Volume 984110.1007/978-3-319-44618-9_5(83-103)Online publication date: 31-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-319-44618-9_5
Fujisaki E(2016)Improving Practical UC-Secure Commitments Based on the DDH AssumptionProceedings of the 10th International Conference on Security and Cryptography for Networks - Volume 984110.1007/978-3-319-44618-9_14(257-272)Online publication date: 31-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-319-44618-9_14
Kawai YHanaoka GOhta KKunihiro N(2016)A limitation on security evaluation of cryptographic primitives with fixed keysSecurity and Communication Networks10.1002/sec.14579:12(1663-1675)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1002/sec.1457
Nuñez DAgudo ILopez J(2016)On the application of generic CCA-secure transformations to proxy re-encryptionSecurity and Communication Networks10.1002/sec.14349:12(1769-1785)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1002/sec.1434
Manulis MPoettering BStebila D(2014)Plaintext awareness in identity-based key encapsulationInternational Journal of Information Security10.1007/s10207-013-0218-513:1(25-49)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s10207-013-0218-5
Matsuda THanaoka G(2014)Chosen Ciphertext Security via UCEProceedings of the 17th International Conference on Public-Key Cryptography --- PKC 2014 - Volume 838310.1007/978-3-642-54631-0_4(56-76)Online publication date: 26-Mar-2014
https://dl.acm.org/doi/10.1007/978-3-642-54631-0_4
Das ADutta SAdhikari A(2013)Indistinguishability against Chosen Ciphertext Verification Attack RevisitedProceedings of the 7th International Conference on Provable Security - Volume 820910.1007/978-3-642-41227-1_6(104-120)Online publication date: 23-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-642-41227-1_6
Show More Cited By

View Options

View options

Get Access

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