How secure is deterministic encryption?

Mihir Bellare, Rafael Dowsley, Sriram Keelveedhi

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

6 Citations (Scopus)


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): • 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. • 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. • 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.

Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2015
Subtitle of host publication18th IACR International Conference on Practice and Theory in Public-Key Cryptography Gaithersburg, MD, USA, March 30 – April 1, 2015 Proceedings
EditorsJonathan Katz
Place of PublicationBerlin Germany
Number of pages22
ISBN (Electronic)9783662464465
ISBN (Print)9783662464465
Publication statusPublished - 2015
Externally publishedYes
EventInternational Conference on Practice and Theory in Public Key Cryptography 2015 - Gaithersburg, United States of America
Duration: 30 Mar 20151 Apr 2015
Conference number: 18th (Proceedings) (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Practice and Theory in Public Key Cryptography 2015
Abbreviated titlePKC 2015
Country/TerritoryUnited States of America
Internet address

Cite this