Paper 2013/681

Public-Key Encryption with Weak Randomness: Security against Strong Chosen Distribution Attacks

Damien Vergnaud and David Xiao

Abstract

Chosen Distribution Attacks (CDA) were introduced by Bellare et al. (Asiacrypt '09) to model attacks where an adversary can control the distribution of both messages and random coins used in an encryption scheme. One important restriction in their definition is that the distributions chosen by the adversary cannot depend on the public key being attacked, and they show that some restriction of this form is necessary (for the same reasons that secure deterministic encryption is impossible if we allow arbitrary dependence between the plaintext distributions and the public key). Subsequently Raghunathan et al. (Eurocrypt '13) showed how to relax this restriction by allowing the message/randomness distributions to depend on the public key as long as the distributions belong to a family of bounded size fixed before the public key is known. We extend the definition further to what we call Strong Chosen Distribution Attacks where the message/randomness distributions may depend on the public key as long as certain entropy conditions are satisfied. Our security model comes from a natural model of attack where an adversary infiltrates the encryption system and installs a trojan program prior to knowing the public key, and subsequently is allowed limited communication with the trojan program. We present secure constructions in the standard and random oracle models both with and without decryption oracles (corresponding to CPA or CCA security). We also prove that our definition simultaneously generalizes previous definitions in this line of work.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
public-key cryptographyweak randomnesslossy trapdoor functionsdeterministic encryption
Contact author(s)
david xiao @ gmail com
History
2013-10-24: received
Short URL
https://ia.cr/2013/681
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/681,
      author = {Damien Vergnaud and David Xiao},
      title = {Public-Key Encryption with Weak Randomness: Security against Strong Chosen Distribution Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2013/681},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/681}},
      url = {https://eprint.iacr.org/2013/681}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.