## CryptoDB

### Paper: Efficient Encryption for Rich Message Spaces Under General Assumptions

Authors: Alexander Russell Hong Wang URL: http://eprint.iacr.org/2001/028 Search ePrint Search Google We present a new family of public-key encryption schemes which combine modest computational demands with provable security guarantees under only general assumptions. The schemes may be realized with any one-way trapdoor permutation, and provide a notion of security corresponding to semantic security under the condition that the message space has sufficient entropy. Furthermore, these schemes can be implemented with very few applications of the underlying one-way permutation: schemes which provide security for message spaces in $\{0,1\}^n$ with minimum entropy $n - \ell$ can be realized with $\ell + w(k)\log k$ applications of the underlying one-way trapdoor permutation. Here $k$ is the security parameter and $w(k)$ is any function which tends to infinity. In comparison, extant systems offering full semantic security require roughly $n$ applications of the underlying one-way trapdoor permutation. Finally, we give a simplified proof of a fundamental elision lemma'' of Goldwasser and Micali.
##### BibTeX
@misc{eprint-2001-11440,
title={Efficient Encryption for Rich Message Spaces Under General Assumptions},
booktitle={IACR Eprint archive},
keywords={public-key cryptography /},
url={http://eprint.iacr.org/2001/028},
note={ acr@cse.uconn.edu 11415 received 3 Apr 2001},
author={Alexander Russell and Hong Wang},
year=2001
}