International Association for Cryptologic Research

International Association
for Cryptologic Research


On the Impossibility of Algebraic NIZK In Pairing-Free Groups

Emanuele Giunta , IMDEA Software Institute
DOI: 10.1007/978-3-031-38551-3_22 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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 \textit{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.
  title={On the Impossibility of Algebraic NIZK In Pairing-Free Groups},
  author={Emanuele Giunta},