Trading One-Wayness Against Chosen-Ciphertext Security in Factoring-Based Encryption

We revisit a long-lived folklore impossibility result for factoring-based encryption and properly establish that reaching maximally secure one-wayness (i.e. equivalent to factoring) and resisting chosen-ciphertext attacks (CCA) are incompatible goals for single-key cryptosystems. We pinpoint two tradeoffs between security notions in the standard model that have always remained unnoticed in the Random Oracle (RO) model. These imply that simple RO-model schemes such as Rabin/RW-SAEP[+]/OAEP[+][+], EPOC-2, etc. admit

no

instantiation in the standard model which CCA security is equivalent to factoring via a key-preserving reduction. We extend this impossibility to

arbitrary

reductions assuming non-malleable key generation, a property capturing the intuition that factoring a modulus

n

should not be any easier when given a factoring oracle for moduli

n

′≠

n

. The only known countermeasures against our impossibility results, besides malleable key generation, are the inclusion of an additional random string in the public key, or encryption twinning as in Naor-Yung or Dolev-Dwork-Naor constructions.