CCA Secure Black Box Commitments From KDM-Security Against Non-uniform Adversaries

Abstract

In this work, we show that we can modify the construction of Garg, Khurana, Lu, and Waters for CCA-secure commitments [11] and replace their hinting PRG with injective extension primitive with KDM-secure encryption. We will present our results in two steps. First, we prove that Brakerski and Goldwasser public-key encryption scheme [5], which is instantiated from subgroup indistinguishability assumption, satisfies non-adaptive KDM-security even when the adversary is given an evaluation of a hard-to-invert function on the secret key. We will call this security notion non-adaptive KDM security under auxillary input. Then, we will modify the construction of Garg et al. to build a tag amplification compiler [11] and prove that we can replace their modified hinting PRG construction with this new notion of KDM-secure encryption under auxiliary input under subexponential quadratic residuosity (QR) and subexponential one-way function (OWF) assumptions.