This paper presents a general methodology for constructing efficient non-interactive zero-knowledge (NIZK) and non-interactive witness-indistinguishable (NIWI) proofs for statements involving bilinear groups. The authors address the inefficiency of previous NIZK proofs, which often required reductions to NP-complete languages like Circuit Satisfiability, leading to large proof sizes. Their approach directly works with bilinear groups, avoiding such reductions and enabling efficient proofs for practical cryptographic protocols.
The paper introduces a framework based on modules over commutative rings with bilinear maps, allowing for the expression of a wide range of statements. It defines a bilinear group as a triple of cyclic groups with a bilinear map and discusses three instantiations of bilinear groups based on different cryptographic assumptions: composite order groups, prime order groups with the symmetric external Diffie-Hellman (SXDH) assumption, and prime order groups with the decisional linear (DLIN) assumption.
The authors develop techniques for constructing NIWI and NIZK proofs for equations over bilinear groups, including pairing product equations, multi-scalar multiplication equations in $ G_1 $ and $ G_2 $, and quadratic equations in $ Z_n $. These proofs are non-interactive, allowing them to be used in contexts where interaction is undesirable or impossible. The proofs are shown to have perfect completeness, perfect soundness, and composable witness indistinguishability.
The paper also demonstrates that these proofs can be transformed into zero-knowledge proofs, leveraging the trapdoor opening capability of certain commitments. This enables the construction of efficient NIZK proofs for various cryptographic applications, including pairing product equations, multi-scalar multiplication equations, and quadratic equations in $ Z_n $.
The authors provide a detailed analysis of the efficiency of their constructions, showing that the size of the proofs is constant per equation, regardless of the number of variables. The paper concludes with a classification of NIZK proofs based on their usefulness and provides a formal proof of the security properties of their constructions.This paper presents a general methodology for constructing efficient non-interactive zero-knowledge (NIZK) and non-interactive witness-indistinguishable (NIWI) proofs for statements involving bilinear groups. The authors address the inefficiency of previous NIZK proofs, which often required reductions to NP-complete languages like Circuit Satisfiability, leading to large proof sizes. Their approach directly works with bilinear groups, avoiding such reductions and enabling efficient proofs for practical cryptographic protocols.
The paper introduces a framework based on modules over commutative rings with bilinear maps, allowing for the expression of a wide range of statements. It defines a bilinear group as a triple of cyclic groups with a bilinear map and discusses three instantiations of bilinear groups based on different cryptographic assumptions: composite order groups, prime order groups with the symmetric external Diffie-Hellman (SXDH) assumption, and prime order groups with the decisional linear (DLIN) assumption.
The authors develop techniques for constructing NIWI and NIZK proofs for equations over bilinear groups, including pairing product equations, multi-scalar multiplication equations in $ G_1 $ and $ G_2 $, and quadratic equations in $ Z_n $. These proofs are non-interactive, allowing them to be used in contexts where interaction is undesirable or impossible. The proofs are shown to have perfect completeness, perfect soundness, and composable witness indistinguishability.
The paper also demonstrates that these proofs can be transformed into zero-knowledge proofs, leveraging the trapdoor opening capability of certain commitments. This enables the construction of efficient NIZK proofs for various cryptographic applications, including pairing product equations, multi-scalar multiplication equations, and quadratic equations in $ Z_n $.
The authors provide a detailed analysis of the efficiency of their constructions, showing that the size of the proofs is constant per equation, regardless of the number of variables. The paper concludes with a classification of NIZK proofs based on their usefulness and provides a formal proof of the security properties of their constructions.