Paper 2015/792

Standard Security Does Not Imply Indistinguishability Under Selective Opening

Dennis Hofheinz, Vanishree Rao, and Daniel Wichs

Abstract

In a selective opening attack (SOA) on an encryption scheme, the adversary is given a collection of ciphertexts and selectively chooses to see some subset of them ``opened'', meaning that the messages and the encryption randomness are revealed to her. A scheme is SOA secure if the data contained in the unopened ciphertexts remains hidden. A fundamental question is whether every CPA secure scheme is necessarily also SOA secure. The work of Bellare et al. (EUROCRYPT '12) gives a partial negative answer by showing that some CPA secure schemes do not satisfy a simulation-based definition of SOA security called SIM-SOA. However, until now, it remained possible that every CPA secure scheme satisfies an indistinguishability-based definition of SOA security called IND-SOA. In this work, we resolve the above question in the negative and construct a highly contrived encryption scheme which is CPA (and even CCA) secure but is not IND-SOA secure. In fact, it is broken in a very obvious sense by a selective opening attack as follows. A random value is secret-shared via Shamir's scheme so that any t out of n shares reveal no information about the shared value. The n shares are individually encrypted under a common public key and the n resulting ciphertexts are given to the adversary who selectively chooses to see t of the ciphertexts opened. Counter-intuitively, this suffices for the adversary to completely recover the shared value. Our contrived scheme relies on strong assumptions: public-coin differing inputs obfuscation and a certain type of correlation intractable hash functions. We also extend our negative result to the setting of SOA attacks with key opening (IND-SOA-K) where the adversary is given a collection of ciphertexts under different public keys and selectively chooses to see some subset of the secret keys.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2016
Keywords
selective opening attackencryption scheme
Contact author(s)
vanishree @ ucla edu
History
2019-01-26: revised
2015-08-10: received
See all versions
Short URL
https://ia.cr/2015/792
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/792,
      author = {Dennis Hofheinz and Vanishree Rao and Daniel Wichs},
      title = {Standard Security Does Not Imply Indistinguishability Under Selective Opening},
      howpublished = {Cryptology ePrint Archive, Paper 2015/792},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/792}},
      url = {https://eprint.iacr.org/2015/792}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.