Cryptology ePrint Archive: Report 2005/382

One-Wayness Equivalent to General Factoring

Kaoru Kurosawa and Tsuyoshi Takagi

Abstract: This paper shows the first practical semantically secure public-key encryption scheme such that its one-wayness is equivalent to {\it general} factoring in the {\it standard} model (in the sense of IND-CPA).

Next our proof technique is applied to Rabin-Paillier encryption scheme and a variant of RSA-Paillier encryption scheme to prove their exactly tight one-wayness.

Category / Keywords: public-key cryptography /

Publication Info: A preliminary version was presented at ASIACRYPT 2003.

Date: received 20 Oct 2005, last revised 24 Oct 2005

Contact author: kurosawa at cis ibaraki ac jp

Available format(s): PDF | BibTeX Citation

Note: In particular, Sec.7 is new.

Version: 20051025:055849 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]