Cryptology ePrint Archive: Report 2019/293

Impossibility of Strong KDM Security with Auxiliary Input

Cody Freitag and 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.

Category / Keywords: foundations / KDM Security, Impossibility

Date: received 13 Mar 2019

Contact author: cfreitag at cs cornell edu, komargodski at cornell edu, rafael at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20190320:102214 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]