Miniature CCA2 PK Encryption : Tight Security Without Redundancy

By Xavier Boyen.

In Advances in Cryptology (ASIACRYPT 2007), volume 4833 of Lecture Notes in Computer Science, pages 485-501. Springer, 2007.

Abstract

We present a minimalist public-key cryptosystem, as compact as ElGamal, but with adaptive chosen-ciphertext security under the gap Diffie-Hellman assumption in the random oracle model. The novelty is a dual-hash device that provides tight redundancy-free implicit validation. Compared to previous constructions, ours features a tight security reduction, both in efficacy and efficiency, to a classic and essentially non-interactive complexity assumption, and without resorting to asymmetric/symmetric-key hybrid constructions. The system is very compact: on elliptic curves with 80-bit security, a 160-bit plaintext becomes a 320-bit ciphertext. It is also very simple and has a number of practical advantages, and we hope to see it adopted widely.

Material

- published paper (PS) (PDF) (also accessible from the publisher) © IACR
- longer version (PS) (PDF)
- presentation slides (HTML)

Reference

@InProceedings{Boyen:ASIACRYPT-2007:miniccapke,
  author = {Xavier Boyen},
  title = {Miniature {CCA2} {PK} Encryption : Tight Security Without Redundancy},
  booktitle = {Advances in Cryptology---ASIACRYPT 2007},
  series = {Lecture Notes in Computer Science},
  volume = {4833},
  pages = {485--501},
  publisher = {Berlin: Springer-Verlag},
  year = {2007},
  note = {Available at \url{http://www.cs.stanford.edu/~xb/asiacrypt07/}}
}