Cryptology ePrint Archive: Report 2016/688

Bounded KDM Security from iO and OWF

Antonio Marcedone and 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.

Category / Keywords: foundations / obfuscation, KDM security, key dependent message security

Original Publication (with major differences): Security and Cryptography for Networks, SCN 2016

Date: received 9 Jul 2016

Contact author: marcedone at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20160712:193815 (All versions of this report)

Short URL: ia.cr/2016/688