Efficient KEMs with partial message recovery

Constructing efficient and secure encryption schemes is an important motivation for modern cryptographic research. We propose simple and secure constructions of hybrid encryption schemes that aim to keep message expansion to a minimum, in particular for RSA-based protocols. We show that one can encrypt using RSA a message of length |m| bits, at a security level equivalent to a block cipher of k bits in security, in |m|+4k + 2 bits. This is therefore independent of how large the RSA key length grows as a function of k. Our constructions are natural and highly practical, but do not appear to have been given any previous formal treatment.