Paper 2023/897

On the Impossibility of Algebraic NIZK In Pairing-Free Groups

Emanuele Giunta, IMDEA Software Institute, Universidad Politecnica de Madrid

Non-Interactive Zero-Knowledge proofs (NIZK) allow a prover to convince a verifier that a statement is true by sending only one message and without conveying any other information. In the CRS model, many instantiations have been proposed from group-theoretic assumptions. On the one hand, some of these constructions use the group structure in a black-box way but rely on pairings, an example being the celebrated Groth-Sahai proof system. On the other hand, a recent line of research realized NIZKs from sub-exponential DDH in pairing-free groups using Correlation Intractable Hash functions, but at the price of making non black-box usage of the group. As of today no construction is known to simultaneously reduce its security to pairing-free group problems and to use the underlying group in a black-box way. This is indeed not a coincidence: in this paper, we prove that for a large class of NIZK either a pairing-free group is used non black-box by relying on element representation, or security reduces to external hardness assumptions. More specifically our impossibility applies to two incomparable cases. The first one covers Arguments of Knowledge (AoK) which proves that a preimage under a given one way function is known. The second one covers NIZK (not necessarily AoK) for hard subset problems, which captures relations such as DDH, Decision-Linear and Matrix-DDH.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2023
NIZKGeneric Group ModelBlack-Box Separation
Contact author(s)
emanuele giunta @ imdea org
2023-06-12: approved
2023-06-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Emanuele Giunta},
      title = {On the Impossibility of Algebraic {NIZK} In Pairing-Free Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2023/897},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.