Paper 2015/853

Standard Security Does Imply Security Against Selective Opening for Markov Distributions

Georg Fuchsbauer, Felix Heuer, Eike Kiltz, and Krzysztof Pietrzak

Abstract

About three decades ago it was realized that implementing private channels between parties which can be adaptively corrupted requires an encryption scheme that is secure against selective opening attacks. Whether standard (IND-CPA) security implies security against selective opening attacks has been a major open question since. The only known reduction from selective opening to IND-CPA security loses an exponential factor. A polynomial reduction is only known for the very special case where the distribution considered in the selective opening security experiment is a product distribution, i.e., the messages are samples independent from each other. In this paper we give a reduction whose loss is quantified via the dependence graph (where message dependencies correspond to edges) of the underlying message distribution. In particular, for some concrete distributions including Markov distributions, our reduction is polynomial.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in TCC 2016
Keywords
public key encryptionselective opening securityMarkovIND-CPAIND-SO-CPA
Contact author(s)
gfuchsbauer @ ist ac at
History
2015-11-25: revised
2015-09-06: received
See all versions
Short URL
https://ia.cr/2015/853
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/853,
      author = {Georg Fuchsbauer and Felix Heuer and Eike Kiltz and Krzysztof Pietrzak},
      title = {Standard Security Does Imply Security Against Selective Opening for Markov Distributions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/853},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/853}},
      url = {https://eprint.iacr.org/2015/853}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.