Optimal Asymmetric Encryption -- How to Encrypt with RSA

Authors: Mihir Bellare and Phillip Rogaway

Reference: Advances in Cryptology - EUROCRYPT '94, Lecture Notes in Computer Science, Vol. 950, A. De Santis, ed., Springer-Verlag, 1995.

Abstract: Given an arbitrary k-bit to k-bit trapdoor permutation~f and a hash function, we exhibit an encryption scheme for which (i) any string x of length slightly less than k bits can be encrypted as f(r_x), where r_x is a simple probabilistic encoding of $x$ depending on the hash function; and (ii) the scheme can be proven semantically secure assuming the hash function is "ideal." Moreover, a slightly enhanced scheme is shown to have the property that the adversary can create ciphertexts only of strings for which she "knows" the corresponding plaintexts- such a scheme is not only semantically secure but also non-malleable and secure against chosen-ciphertext attack.


Full paper: Available as compressed postscript, postscript, or pdf.


Rogaway's home page.