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

Available format(s)
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
Short URL
https://ia.cr/2016/688

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.