Bounded KDM Security from iO and OWF

Antonio Marcedone; Rafael Pass; abhi shelat

Paper 2016/688

Bounded KDM Security from iO and OWF

Antonio Marcedone, Rafael Pass, and abhi shelat

Abstract

To date, all constructions in the standard model (i.e., without random oracles) of Bounded Key-Dependent Message (KDM) secure (or even just circularly-secure) encryption schemes rely on specific assumptions (LWE, DDH, QR or DCR); all of these assumptions are known to imply the existence of collision-resistant hash functions. In this work, we demonstrate the existence of bounded KDM secure encryption assuming indistinguishability obfsucation for $P / p o l y$ and just one-way functions. Relying on the recent result of Asharov and Segev (STOC'15), this yields the first construction of a Bounded KDM secure (or even circularly secure) encryption scheme from an assumption that provably does not imply collision-resistant hash functions w.r.t. black-box constructions. Combining this with prior constructions, we show how to augment this Bounded KDM scheme into a Bounded CCA2-KDM scheme.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Major revision. Security and Cryptography for Networks, SCN 2016
Keywords: obfuscation KDM security key dependent message security
Contact author(s): marcedone @ cs cornell edu
History: 2016-07-12: received
Short URL: https://ia.cr/2016/688
License: CC BY

BibTeX

@misc{cryptoeprint:2016/688,
      author = {Antonio Marcedone and Rafael Pass and abhi shelat},
      title = {Bounded {KDM} Security from {iO} and {OWF}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/688},
      year = {2016},
      url = {https://eprint.iacr.org/2016/688}
}