Cryptology ePrint Archive: Report 2015/853
Standard Security Does Imply Security Against Selective Opening for Markov Distributions
Georg Fuchsbauer and Felix Heuer and 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.
Category / Keywords: public-key cryptography / public key encryption, selective opening security, Markov, IND-CPA, IND-SO-CPA
Original Publication (in the same form): IACR-TCC-2016
Date: received 3 Sep 2015, last revised 25 Nov 2015
Contact author: gfuchsbauer at ist ac at
Available format(s): PDF | BibTeX Citation
Version: 20151125:113401 (All versions of this report)
Short URL: ia.cr/2015/853
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]