Impossibility of Strong KDM Security with Auxiliary Input

Cody Freitag; Ilan Komargodski; Rafael Pass

Paper 2019/293

Impossibility of Strong KDM Security with Auxiliary Input

Cody Freitag, Ilan Komargodski, and Rafael Pass

Abstract

In this note, we show that a strong notion of KDM security cannot be obtained by any encryption scheme in the auxiliary input setting, assuming Learning With Errors (LWE) and one-way permutations. The notion of security we deal with guarantees that for any (possibly inefficient) function $f$ , it is computationally hard to distinguish between an encryption of 0s and an encryption of f(pk, z), where pk is the public key and z is the auxiliary input. Furthermore, we show that this holds even when restricted to bounded-length auxiliary input where z is much shorter than pk under the additional assumption that (non-leveled) fully homomorphic encryption exists.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: KDM Security Impossibility
Contact author(s): cfreitag @ cs cornell edu
komargodski @ cornell edu
rafael @ cs cornell edu
History: 2019-03-20: received
Short URL: https://ia.cr/2019/293
License: CC BY

BibTeX

@misc{cryptoeprint:2019/293,
      author = {Cody Freitag and Ilan Komargodski and Rafael Pass},
      title = {Impossibility of Strong {KDM} Security with Auxiliary Input},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/293},
      year = {2019},
      url = {https://eprint.iacr.org/2019/293}
}