Rafail Ostrovsky - Publications

On Selective−Opening Attacks Against

Rafail Ostrovsky, Vanishere Rao, Ivan visconti

Abstract:

At the FOCS'99, Dwork et al put fort the notion of‘ selective−opening attacks’ (SOAs, for short). In the literature, security such attacks has been formalized via indistinguishability −based and simulation− based and simulation−based notions, respectively called IND−SO−C PA security and SIM−CPA security. Furthermore; the IND−SO−CPA notion has been studied under two flavors−weak−IND−SO− CPA and full−IND−SO−CPA security. At Eurocrypt′09, Bellare et al showed the first positive results on SOA security of encryption schemes : 1) any losyencryption scheme is weak−IND−SO−CPA secure; 2) any lossy encryption scheme with efficient openability is SIM−SO−CPA secure.

Despite rich further work on SOA security, the ( un ) feasibility of full −−IND−SO−CPA remains a major open problem in the area of SOA security. The elusive nature of the full −−IND−SO−CPA notion of security is attributed to a specific aspect of the security game , namely, the challenger requiring to perform a super−polynomialtime task. Not only do we not know whether there exists a scheme that is full IND−SO−CPA secure, but we also do not know concrete attacks against popular schemes such as the ELGamal and Cramer −Shoup schemes in the full& IND−SO−CPA model.

The Contribution of our work is three−fold.

1 Motivated by the difficulty in understanding (un) feasibility of the full IND−SO−CPA notion, we study a variant of this notion that is closer in spirit to the IND−SO−CPAnotion but still embodies the security captured by the full −IND−SO−CPAnotion. We observe that the weak from our variation does not introduce any significant change to the weak−IND−SO−CPA notion;that is, the weak form of our notion is equivalent to the weak−IND−SO−CPA notion.

2 In terestingly, we can show that a large class of encryption schemes can be proven insecure for the form of our notion. The large class includes most known constructions of weakͨIND−SO−CPA secure schemes and SIMSO−CPA secure schemes and also popular schemes like the ELGamal and Cramer−Shoup schemes.

3 Our third contribution studies the complexity of SIMSO−CPAsecurity. Complementing the results of Bellare et al, we show that lossiness is not necessary to achieve SIMSO−CPA security. More specifically, we present a SIMSO−CPAscheme that is not lossy encryption scheme(regardless of efficient openability). Since SIMSO−CPA security implies weak;−IND−SOCPAsecurity, it follows as a corollary that the converses of both the implications proved by Bellare et al do not hold. Furthermore; as a corollary of our techniques, on a slightly unrelated but useful note, we obtain that lossiness is not required to obtain non-committing encryption. Previously, at Eurocrypt′09 Fehr et al showed a construction of a non−committing encryption scheme from trapdoor permutations and this scheme was ,as noted by the authors, possibly not lossy. Our schem amounts to the first construction of non−committing encryption scheme that is provably not lossy.

comment: SCN 2014 PP: 578−597

Fetch PDF file of the paper