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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. MAJOR revision.Security and Cryptography for Networks, SCN 2016
Keywords
obfuscationKDM securitykey dependent message security
Contact author(s)
marcedone @ cs cornell edu
History
2016-07-12: received
Short URL
https://ia.cr/2016/688
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/688}},
      url = {https://eprint.iacr.org/2016/688}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.