Paper 2001/028

Efficient Encryption for Rich Message Spaces Under General Assumptions

Alexander Russell and Hong Wang

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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
acr @ cse uconn edu
History
2001-04-03: received
Short URL
https://ia.cr/2001/028
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/028,
      author = {Alexander Russell and Hong Wang},
      title = {Efficient Encryption for Rich Message Spaces Under General Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2001/028},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/028}},
      url = {https://eprint.iacr.org/2001/028}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.