Optimal asymmetric encryption

M. Bellare, P. Rogaway

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( gamma /sub x/),
where gamma /sub x/ is and 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.