Strengthening Security of RSA-OAEP

OAEP is one of the few standardized and widely deployed public-key encryption schemes. It was designed by Bellare and Rogaway as a scheme based on a trapdoor permutation such as RSA. RSA-OAEP is standardized in RSA’s PKCS #1 v2.1 and is part of several standards. RSA-OAEP was shown to be IND-CCA secure in the random oracle model under the standard RSA assumption. However, the reduction is not tight, meaning that the guaranteed level of security is not very high for a practical parameter choice. We first observe that the situation is even worse because the analysis was done in the single-query setting, i.e. where an adversary gets a single challenge ciphertext. This does not take into account the fact that in reality an adversary can observe multiple ciphertexts of related messages. The results about the multi-query setting imply that the guaranteed concrete security can degrade by a factor of

q

, which is the number of challenge ciphertexts an adversary can get. We re-visit a very simple but not well-known modification of the RSA-OAEP encryption which asks that the RSA function is only applied to a part of the OAEP transform. We show that in addition to the previously shown fact that security of this scheme is tightly related to the hardness of the RSA problem, security does not degrade as the number of ciphertexts an adversary can see increases. Moreover, this scheme can be used to encrypt long messages without using hybrid encryption. We believe that this modification to the RSA-OAEP is easy to implement, and the benefits it provides deserves the attention of standard bodies.