A Chosen-Cipher Secure Encryption Scheme Tightly as Secure as Factoring

Eiichiro FUJISAKI  Tatsuaki OKAMOTO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A   No.1   pp.179-187
Publication Date: 2001/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
chosen-cipher security,  factoring,  random oracle,  exact security,  

Full Text: PDF(265.5KB)>>
Buy this Article

At Eurocrypt'98, Okamoto and Uchiyama presented a new trap-door (one-way) function based on factoring, while Fujisaki and Okamoto, at CRYPTO'99, showed a generic conversion from just one-way encryption to chosen-cipher secure encryption in the random oracle model. This paper shows that the result of combining both schemes is well harmonized (rather than an arbitrary combination) and, in the sense of exact security, boosts the level of security more than would be expected from [6]--The security of the scheme yielded by the combination is tightly reduced from factoring. This paper also gives a rigorous description of the new scheme, because this type of encryption may suffer serious damage if poorly implemented. The proposed scheme is at least as efficient as any other chosen-cipher secure asymmetric encryption scheme such as [2],[4],[13].