Paper 2022/1032

On Non-uniform Security for Black-box Non-Interactive CCA Commitments

Rachit Garg, The University of Texas at Austin
Dakshita Khurana, University of Illinois Urbana-Champaign
George Lu, The University of Texas at Austin
Brent Waters, The University of Texas at Austin

We obtain a black-box construction of non-interactive CCA commitments against non-uniform adversaries. This makes black-box use of an appropriate base commitment scheme for small tag spaces, variants of sub-exponential hinting PRG (Koppula and Waters, Crypto 2019) and variants of keyless sub-exponentially collision-resistant hash function with security against non-uniform adversaries (Bitansky, Kalai and Paneth, STOC 2018 and Bitansky and Lin, TCC 2018). All prior works on non-interactive non-malleable or CCA commitments without setup first construct a "base" scheme for a relatively small identity/tag space, and then build a tag amplification compiler to obtain commitments for an exponential-sized space of identities. Prior black-box constructions either add multiple rounds of interaction (Goyal, Lee, Ostrovsky and Visconti, FOCS 2012) or only achieve security against uniform adversaries (Garg, Khurana, Lu and Waters, Eurocrypt 2021). Our key technical contribution is a novel tag amplification compiler for CCA commitments that replaces the non-interactive proof of consistency required in prior work. Our construction satisfies the strongest known definition of non-malleability, i.e., CCA2 (chosen commitment attack) security. In addition to only making black-box use of the base scheme, our construction replaces sub-exponential NIWIs with sub-exponential hinting PRGs, which can be obtained based on assumptions such as (sub-exponential) CDH or LWE.

Available format(s)
Publication info
non-malleable commitments black-box keyless hash CCA
Contact author(s)
rachg96 @ cs utexas edu
dakshita @ illinois edu
gclu @ utexas edu
bwaters @ cs utexas edu
2022-08-11: approved
2022-08-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rachit Garg and Dakshita Khurana and George Lu and Brent Waters},
      title = {On Non-uniform Security for Black-box Non-Interactive CCA Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1032},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.