Paper 2014/376

How Secure is Deterministic Encryption?

Mihir Bellare, Rafael Dowsley, and Sriram Keelveedhi

Abstract

This paper presents three curious findings about deterministic public-key encryption (D-PKE) that further our understanding of its security, in particular because of the contrast with standard, randomized public-key encryption (R-PKE): (1) It would appear to be a triviality, for any primitive, that security in the standard model implies security in the random-oracle model, and it is certainly true, and easily proven, for R-PKE. For D-PKE it is not clear and depends on details of the definition. In particular we can show it in the non-uniform case but not in the uniform case. (2) The power of selective-opening attacks (SOA) comes from an adversary's ability, upon corrupting a sender, to learn not just the message but also the coins used for encryption. For R-PKE, security is achievable. For D-PKE, where there are no coins, one's first impression may be that SOAs are vacuous and security should be easily achievable. We show instead that SOA-security is impossible, meaning no D-PKE scheme can achieve it. (3) For R-PKE, single-user security implies multi-user security, but we show that there are D-PKE schemes secure for a single user and insecure with two users.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2015
Keywords
Deterministic public-key encryptionrandom-oracle modelselective-opening attack
Contact author(s)
mihir @ eng ucsd edu
History
2015-02-12: revised
2014-05-28: received
See all versions
Short URL
https://ia.cr/2014/376
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/376,
      author = {Mihir Bellare and Rafael Dowsley and Sriram Keelveedhi},
      title = {How Secure is Deterministic Encryption?},
      howpublished = {Cryptology ePrint Archive, Paper 2014/376},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/376}},
      url = {https://eprint.iacr.org/2014/376}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.