Cryptology ePrint Archive: Report 2003/157

Some RSA-based Encryption Schemes with Tight Security Reduction

Kaoru Kurosawa and Tsuyoshi Takagi

Abstract: In this paper, we study some RSA-based semantically secure encryption schemes (IND-CPA) in the standard model. We first derive the exactly tight one-wayness of Rabin-Paillier encryption scheme which assumes that factoring Blum integers is hard. We next propose the first IND-CPA scheme whose one-wayness is equivalent to factoring {\it general} $n=pq$ (not factoring Blum integers). Our reductions of one-wayness are very tight because they require only one decryption-oracle query.

Category / Keywords: public-key cryptography / public-key cryptography, factoring

Publication Info: accepted by Asiacrypt'2003

Date: received 7 Aug 2003

Contact author: kurosawa at cis ibaraki ac jp

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Note: This is a long version.

Version: 20030807:155401 (All versions of this report)

Short URL: ia.cr/2003/157

Discussion forum: Show discussion | Start new discussion