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
[ Cryptology ePrint archive ]