International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Encryption for Rich Message Spaces Under General Assumptions

Authors:
Alexander Russell
Hong Wang
Download:
URL: http://eprint.iacr.org/2001/028
Search ePrint
Search Google
Abstract: 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
}