Paper 2016/688

Bounded KDM Security from iO and OWF

Antonio Marcedone, Rafael Pass, and abhi shelat


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/poly$ 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.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.Security and Cryptography for Networks, SCN 2016
obfuscationKDM securitykey dependent message security
Contact author(s)
marcedone @ cs cornell edu
2016-07-12: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.