News
Groth-Sahai Proofs: Zero to Hero
This blog post assumes a basic knowledge of cryptography, including pairing-based cryptography as well as what (Non-Interactive) Zero-Knowledge proofs are and what they do. The Ali Baba cave is a simple example of Zero-Knowledge proofs for readers who are unfamiliar with the topic of zero-knowledge proof systems.
Zero-Knowledge (ZK) proof systems are foundational technologies that have evolved to power privacy-preserving transactions on blockchains, including infrastructure built by Mysten Labs. Jens Groth and Amit Sahai's seminal work, "Efficient Non-Interactive Proof Systems for Bilinear Groups" [GS08] from Eurocrypt 2008, received the IACR test-of-time award in 2023 due to its impact on many applications like succinct non-interactive arguments. In this blog post, we provide a detailed explanation of this beautiful proof system called Groth-Sahai (GS) proofs and share some interesting applications. Moreover, we elaborate on how to implement GS proofs and prove a simple statement based on them. We then investigate its performance in Python using the Charm-Crypto library [AGM+13].
💡TL;DR: Groth-Sahai proofs offer a relatively efficient method for proving the satisfiability of some quadratic equations in bilinear settings. You can use GS proofs to prove satisfiability of an arithmetic circuit with a proof size that grows linearly in the number of gates and variables. Subsequent zk-SNARKs are more efficient, since they offer constant size proofs. GS proofs still shine in the context of building pairing-based protocols though, since they offer a natural and direct way to prove statements that arise in pairing-based cryptography, without having to first compile the statement to a circuit. Many signatures and other cryptographic schemes that are “structure-preserving” in the sense that they only operate in groups with pairings that have been proposed because statements about them can be proved directly with GS proofs.
Zero-Knowledge proofs [GMR85], and, more importantly, a non-interactive version of them have become standard tools in cryptography. Non-Interactive Zero-Knowledge (NIZK) [BFM88] proof systems allow a prover to convince a skeptical verifier about the validity of a statement in a single round of communication. The zero-knowledge property ensures that the verifier learns nothing beyond the validity of the proof, while soundness guarantees that no malicious prover can convince the verifier of false statements. Throughout the almost 40 years since their invention, researchers have been trying to improve the efficiency of these constructions in various aspects, such as proving time, proof size, verifying complexity, and underlying assumptions, in two possible settings: the Random Oracle Model (ROM) and Common Reference String (CRS) model.
How do GS Proofs compare to recent zk-SNARKs?
Zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) are a family of NIZK with succinct proof size and efficient verification time in the CRS model. An important and widely used variant of them is pairing-based zk-SNARKs that are the main focus of this blog post. However, pairing-based zk-SNARKs were proposed in 2010, approximately two years after the development of the GS proof systems in [Gro10]. One feature that makes zk-SNARKs very interesting compared to other NIZKs is that they can be applied to any nondeterministic polynomial time-language, NP-language in short, in a general fashion efficiently. Achieving this fancy feature often requires a complex and trusted setup, as well as costly proving time in the order of the circuit size. Additionally, zk-SNARKs are based on non-falsifiable assumptions. Loosely speaking, the hardness of these assumptions cannot be proven from the hardness of other well-known assumptions like the Discrete Logarithm problem, nor can it be concluded that they are not secure. Although a bit shaky, it is not a major concern in the community at the moment [GW11].
Similar to zk-SNARKs, Groth-Sahai proofs are also in the CRS model and enable a prover to prove some facts for a class of statements in bilinear groups. As a strong feature, the security of them is proven under the standard assumptions.
💡To better understand the differences between standard and non-standard assumptions, consider the safety ratings of cars. A car's safety rating is evaluated through a 5-star program that assesses its performance in crash tests. Standard assumptions can be thought of as those cars with higher ratings, while non-falsifiable assumptions have no certification. They may receive a high or low rating if tested, but their rating is unknown at the moment. However, it's still important to drive safely, as even a car with the lowest rating can still be safe.
The table below summarizes the main differences between GS proofs, compared to Groth16’s zk-SNARK, which is the most efficient zk-SNARK to date.
💡Table of Comparison. GS proofs are described for a Pairing-Product Equation (PPE) statement where nn denotes the depth of circuit, and NN denotes the number of pairings in any given Pairing-Product Equation (PPE).
Which Class of Statements can be supported then?
As mentioned previously, GS proofs support the satisfiability of several quadratic equations over bilinear pairings. These relations are listed as follows:
Pairing-Product Equations (PPE).
Multi-Scalar multiplication equations in G1G1.
Multi-Scalar multiplication equations in G2G2.
Quadratic equations in ZpZp.
As the PPE relation is the most widely used in GS proofs' applications, we will only discuss them here and leave the other three relations for a future blog post. Let's start with a simple PPE, where e(X,Y)=Te(X,Y)=T. In this relation, the prover wants to prove the knowledge of hidden group elements XX and YY, such that their pairing is equal to a publicly known value TT. The prover can commit to XX and YY (which will be discussed below) to hide them, along with a proof to cancel out the used randomness in the commitment. However, we need to be careful that the proof must be simulatable, which guarantees the zero-knowledge property, and that it is knowledge sound, as shown by Groth and Sahai.
💬 Groth and Sahai proposed two main instantiations: one in symmetric bilinear groups under the decisional 2-linear (DLin) assumption and the other one in asymmetric bilinear groups based on the SXDH assumption. In this blog post, we only discuss GS proofs instantiated based on the SXDH assumptions. This is because it is the most efficient instantiation of the GS proof systems. The SXDH assumption states that the DDH assumption is hard in both groups G1G1 and G2G2.
Main Ingredients
The GS proof system uses a combination of commitment schemes and bilinear maps to create a zero-knowledge proof of a statement.
(Type_III) Bilinear pairings are an efficient mathematical operation that maps two elements from two different (source) groups to a multiplicative (target) group, i.e. G1×G2→GTG1×G2→GT. Pairings are used in various cryptographic applications, such as identity-based encryption and signature schemes and more importantly in the design of zk-SNARKs. The source groups G1G1 and G2G2 are subgroups of elliptic curves (EC). Elliptic curves are a type of mathematical curve commonly used in cryptography. A subgroup is a subset of a larger group that retains the same group structure. We provide the below image as a superficial introduction to elliptic curves, however if you are interested in learning more about bilinear pairings and elliptic curves, we recommend reading this nice blog post [Tom22].
Loosely speaking, an asymmetric pairing takes as input a point on the first curve, G1=⟨G1⟩G1=⟨G1⟩, for example point αG1αG1 (where αα times dot operations “∘∘” (briefly described in above image) are computed over the generator G1G1) and a point on curve G2=⟨G2⟩G2=⟨G2⟩ that has been subjected to the ββ times dot function on G2G2, resulting in point βG2βG2. The pairing maps these two points to a point on the target group GT=⟨e(G1,G2)⟩GT=⟨e(G1,G2)⟩ such that the dot operation is performed on its generator, αβαβ times.
More formally for an efficiently computable bilinear map e:G1×G2→GTe:G1×G2→GT we have:
For all α,β∈Zpα,β∈Zp, e(αG1,βG2)=e(βG1,αG2)=αβe(G1,G2)e(αG1,βG2)=e(βG1,αG2)=αβe(G1,G2).
e(G1,G2)≠1e(G1,G2)=1.
Extended bilinear pairings [GS08] (Tensor product): For any random scalars x1,x2,y1,y2∈Zpx1,x2,y1,y2∈Zp, where pp is the order of groups, the extended bilinear pairing map, E:G12×1×G21×2→GT2×2E:G12×1×G21×2→GT2×2 can be defined as follows:
E((x1G1x2G2),(y1G2y2G2))=(e(x1G1,y1G2)e(x1G1,y2G2)e(x2G1,y1G2)e(x2G1,y2G2)).E((x1G1x2G2),(y1G2y2G2))=(e(x1G1,y1G2)e(x2G1,y1G2)e(x1G1,y2G2)e(x2G1,y2G2)).
Commitment schemes: In the Groth-Sahai proof system, the prover shows the existence of witnesses that satisfy a relation. However to keep the witnesses hidden, the prover commits to them and reveals the public elements. Commitments are a well-known cryptographic primitive with three main algorithms: Setup,CommitSetup,Commit and OpenOpen that satisfy the security properties of hiding and binding. Hiding ensures that the commitment does not reveal anything about the committed message mm, while the binding property guarantees that the committer cannot open a commitment to two distinct messages.
A variant of Pedersen Commitments [GS08]: Pedersen commitments [Ped91] are widely used in various applications. However GS proofs rely on a slightly modified version of this commitment schemes with generators. In a cyclic group G=⟨G⟩G=⟨G⟩ with prime order pp and generator GG, we recall Pedersen commitments with two generators below:
ck←Setup(1κ)ck←Setup(1κ): Take the security parameter κκ and sample two random group elements (V1,V2) ←$G2(V1,V2) ←$G2, and return committing key ck=(V1,V2)ck=(V1,V2).
com←Commit(ck,M)com←Commit(ck,M): To commit to a message M∈GM∈G, sample two random scalars τ1,τ2←$Zpτ1,τ2←$Zp and compute the commitment com=M+τ1V1+τ2V2com=M+τ1V1+τ2V2.
0/1←Open(ck,com,M,τ1,τ2)0/1←Open(ck,com,M,τ1,τ2): Compute com′=M+τ1V1+τ2V2com′=M+τ1V1+τ2V2 and check com′=?comcom′=?com or not.
💡Why two generators?
Roughly speaking, this special commitment scheme enables proof simulation.
Pairing-Product Equations
💡Do you find the equation below difficult to follow? Then skip this section and instead follow the ideas presented in the simple example part. 🙂
In a PPE relation, a prover can prove the knowledge of some hidden group elements that satisfy a relation like the equation (∗)(∗) below.
∑i=1ne(Xi,Bi)+∑j=1me(Aj,Yj)+∑i=1n∑j=1me(Xi,γijYj)=T ,(∗)i=1∑ne(Xi,Bi)+j=1∑me(Aj,Yj)+i=1∑nj=1∑me(Xi,γijYj)=T ,(∗)
Where X1,…,Xn∈G1nX1,…,Xn∈G1n and Y1,…,Ym∈G2mY1,…,Ym∈G2m are the secret variables which the prover wants to prove some facts about. Additionally, B1,…,Bn∈G2nB1,…,Bn∈G2n, A1,…,Am∈G1mA1,…,Am∈G1m, Γ:=γij∈Zpn×mΓ:=γij∈Zpn×m, and T∈GTT∈GT are the constants. If the constant value TT in the described PPE is equal to 1GT1GT, this construction can guarantee the Zero-Knowledge property. Conversely, if there are two public variables that are paired to each other then GS proof only satisfies witness indistinguishability (WI) which is a weaker notion of ZK. However, as Escala and Groth noted in [EG14], the proof system remains zero-knowledge even if the source groups' generators and the public variables are paired with each other and any public variables pairing results to WI.
💡 For simplicity, we ignore the γijγij values and assume that they can be injected into the PPE variables directly. This modification improves code efficiency by reducing the number of group exponentiations in the verification phase by a factor of (n+m)(n+m).
To clarify, many pairing-based signatures can be verified if a pairing product equation (PPE) holds for a message. Therefore, a prover can prove knowledge of hidden signature components and a corresponding message that pass the verification, i.e. satisfy a PPE. We will discuss this useful relation later and its applications to anonymous credential systems.
GS Proofs: How do they work?
As we already mentioned, GS-proofs use the commit-and-prove paradigm; The prover commits to hidden group elements using a set of fresh random values, while the proof carries some form of the used random values to cancel them out during the verification. Thanks to bilinear pairings that enables exponent multiplication over group elements while the commitment enables witness hiding. Note that in GS proofs, the opening function of the commitment scheme is not used, and the witnesses will remain hidden.
💡In some parts, we used a combination of techniques discussed in the initial paper [GS08] and the Escala and Groth paper [EG14]. In order to maintain consistency with the code, we have made slight modifications to the variables and inputs used in the algorithms.
CRS←(Trusted)Setup(1κ)CRS←(Trusted)Setup(1κ): For any security parameter κκ and an asymmetric bilinear pairing description, (G1,G2,GT,p,e,G1,G2)(G1,G2,GT,p,e,G1,G2), the setup can be run independently of the pairing product equations, and the same parameters can be used for multiple equations. The prover and verifier use the same CRS to produce and verify the proof, respectively. The CRS contains four pairs of Pedersen commitment keys: two pairs for the first group G1G1, and two pairs for the second group, G2G2.
CRS=(V10,V11,W10,W11,V20,V21,W20,W22)∈G14×G24.CRS=(V10,V11,W10,W11,V20,V21,W20,W22)∈G14×G24.
💡Note that the setup can be performed transparently using public randomness and random oracle models, and no trust to a central entity is needed and this can be seen as an obvious advantage of GS proofs compared to zk-SNARKs: as they either rely on a trusted party or complex trust mitigation techniques like MPC (ceremonies).
Before describing the committing phase, we need to perform some arithmetization on any given PPE relation. For simplicity, especially in the implementation of this construction, we merge the secret and public variables into two main vectors, X⃗∈G1NX∈G1N and Y⃗∈G2NY∈G2N, where N=n+mN=n+m. These vectors include both public and secret values such that the pairwise pairing operation e(X⃗,Y⃗)=Te(X,Y)=T holds. By defining the vectors this way, we can rewrite the PPE as follows:
e(X⃗,Y⃗)=∑i=1Ne(Xi,Yi)=T.e(X,Y)=i=1∑Ne(Xi,Yi)=T.
We can achieve this by placing all elements from the first group into vector X⃗X and all elements from the second group into vector Y⃗Y, including both public and hidden values. Additionally, we must define identifier vectors C⃗xCx and C⃗yCy to keep track of the hidden and public variables in X⃗X and Y⃗Y, respectively:
Cx[i]={1if X[i]∈witnesses0otherwiseCy[i]={1if Y[i]∈witnesses0otherwiseCx[i]={10if X[i]∈witnessesotherwiseCy[i]={10if Y[i]∈witnessesotherwise
By forming these four vectors we are ready to run the commit function as follows:
Commit(CRS,X⃗,Y⃗,C⃗x,C⃗y)Commit(CRS,X,Y,Cx,Cy): If Cx[i]=1Cx[i]=1, it samples random integers ri1,si1←$Zpri1,si1←$Zp, which enable the witnesses to be hidden, else it assigns randomness to zero to reveal the public values. The commitment to each element Xi∈X⃗Xi∈X includes two commitments, discussed above. The first one is a commitment to the identity value under randomnesses ri1ri1 and si1si1 w.r.t V10V10 and V11V11 keys. The second commitment is to the group element Xi∈G1Xi∈G1 under the same randomnesses, however computed based on the W10W10 and W11W11 commitment keys. In the other words we have:
comXi=(ri1V10+si1V11Xi+ri1W10+si1W11)∈G12×1.comXi=(ri1V10+si1V11Xi+ri1W10+si1W11)∈G12×1.
The prover keeps committing to all elements in X⃗X. As the randomnesses are assigned to zero for public variables, these commitments look as follows:
comXi=(1G1Xi)∈G12×1.comXi=(1G1Xi)∈G12×1.
Similarly, the prover commits to all elements in the second groups, i.e. Yi∈Y⃗Yi∈Y, by sampling random integers ri2ri2 and si2si2, as follows:
comYi=(ri2V20+si2V21Yi+ri2W20+si2W21)∈G21×2comYi=(ri2V20+si2V21Yi+ri2W20+si2W21)∈G21×2
For any public variable in Y⃗Y we have:
comYi=(1G2Yi)∈G21×2.comYi=(1G2Yi)∈G21×2.
Prove(CRS,X⃗,Y⃗,comx⃗,com⃗y,r⃗,s⃗)Prove(CRS,X,Y,comx,comy,r,s): After committing to the witnesses the prover runs the prove algorithm. Note that the proof size is constant and it contains 88 group elements independent of the size of X⃗X and Y⃗Y defined as follows:
πV1=(∑i=1Nri1comYi[0]∑i=1Nri1comYi[1])∈G21×2,πW1=(∑i=1Nsi1comYi[0]∑i=1Nsi1comYi[1])∈G21×2,πV2=(1G1∑i=1Nri2Xi)∈G12×1,πW2=(1G1∑i=1Nsi2Xi)∈G12×1,πV1=(∑i=1Nri1comYi[0]∑i=1Nri1comYi[1])∈G21×2,πW1=(∑i=1Nsi1comYi[0]∑i=1Nsi1comYi[1])∈G21×2,πV2=(1G1∑i=1Nri2Xi)∈G12×1,πW2=(1G1∑i=1Nsi2Xi)∈G12×1,
where comYi[0]comYi[0] and comYi[1]comYi[1] denote the first and second entries in the dual commitment comYicomYi. The prover must first re-randomise the proofs, which allows for the reuse of commitments in the proofs of different statements, even when these statements depend on previous commitments and proofs. Thus the prover samples random integers α,β,γ,δ←$Zp4α,β,γ,δ←$Zp4 and then computes:
πV1=(∑i=1Nri1comYi[0]+αV20+βW20∑i=1Nri1comYi[1]+αV21+βW21)∈G22,πW1=(∑i=1Nsi1comYi[0]+γV20+δW20∑i=1Nsi1comYi[1]+γV21+δW21)∈G22,πV2=(−αV10−γW10∑i=1Nri2Xi−αV11−γW11)∈G12,πW2=(−βV10−δW10∑i=1Nsi2Xi−βV11−δW11)∈G12.πV1=(∑i=1Nri1comYi[0]+αV20+βW20∑i=1Nri1comYi[1]+αV21+βW21)∈G22,πW1=(∑i=1Nsi1comYi[0]+γV20+δW20∑i=1Nsi1comYi[1]+γV21+δW21)∈G22,πV2=(−αV10−γW10∑i=1Nri2Xi−αV11−γW11)∈G12,πW2=(−βV10−δW10∑i=1Nsi2Xi−βV11−δW11)∈G12.
This gives us the randomised proof π=(πV1,πV2,πW1,πW2)π=(πV1,πV2,πW1,πW2) that is the final output of this algorithm.
Verify(CRS,π,com⃗X,com⃗Y)Verify(CRS,π,comX,comY): The verifier checks the validity of the proof by checking the following equation:
∑i=1NE(comXi,comYi)=T+E((V10V11),πV1)+E((W10W11),πW1)+E(πV2,(V20V21))+E(πW2,(W20W21)).i=1∑NE(comXi,comYi)=T+E((V10V11),πV1)+E((W10W11),πW1)+E(πV2,(V20V21))+E(πW2,(W20W21)).
💡 To check the validity of a proof created based on a PPE of NN values, the verifier by running the above function needs to compute 4(N+4)4(N+4) pairings. The factor 44 mainly comes from the extended pairing EE that we defined above and of course this is not practical in most cases especially when NN is sufficiently large. Herold et al. in [HHK+17] discuss a nice technique of aggregation for GS proofs and we use a well-known batching techniques to reduce the number of pairings needed. We will not delve into the details of the technique used. This reduces the number of pairings to only N+4N+4 to check the validity of the same proof that is a considerable improvement. Note that the batched verification algorithm is not deterministic. However, one feature that makes it more interesting is that it only needs 4 more pairings compared to the PPE checking assuming all elements are in plain. Thus any construction that can be verified by pairing equation checkings can be lifted to a zero-knowledge proof. Instead of revealing all inputs, the prover can hide some of them and now with just 4 more pairings the statement is still verifiable.
A Simple Example: Proof of knowledge of a BLS signature with public message
BLS signatures [BLS01] over asymmetric bilinear pairings are a widely used scheme in different applications. Imagine the case that a user wants to prove the knowledge of a secret BLS signature, σ=skH(m)σ=skH(m) on a public message mm to a verifier, where H:{0,1}∗→G1H:{0,1}∗→G1 is a hash-to-curve function. This scenario for instance occurs in anonymous credential systems. In that setting usually both the message and the signature must be kept hidden and the prover only proves a predicate on message (unlinkability property). However, for simplicity in this example we assume the message to be public (if we opted to also hide the message, then we would have to prove knowledge of the pre-image of the hash function which requires zk-SNARKs). Coming back to BLS signatures, a signature σσ is valid if the following equation holds:
e(H(m),vk)=e(σ,G2)e(H(m),vk)=e(σ,G2)
To turn this equation to a PPE, we can write:
e(H(m),vk)+e(σ,−G2)=1GT.e(H(m),vk)+e(σ,−G2)=1GT.
Thus we can define the vector X⃗=(H(m),σ)X=(H(m),σ) and also Y⃗=(vk,−G2)Y=(vk,−G2). As we agreed only the signature must remain hidden then we have, C⃗x=(0,1)Cx=(0,1) and C⃗y=(0,0)Cy=(0,0). The prover samples two integers r21,s21←$Zp∗r21,s21←$Zp∗ and then forms r⃗=([0,0],[r21,s21])r=([0,0],[r21,s21]) and s⃗=([0,0],[0,0])s=([0,0],[0,0]), and commits to the variables as follows:
comH(m)=(1G1H(m))∈G12×1,comvk=(1G2vk)∈G21×2,comσ=(r21V10+s21V11σ+r21W10+s21W11)∈G12×1,comG2=(1G2−G2)∈G21×2.comH(m)=(1G1H(m))∈G12×1,comvk=(1G2vk)∈G21×2,comσ=(r21V10+s21V11σ+r21W10+s21W11)∈G12×1,comG2=(1G2−G2)∈G21×2.
Now the prover first samples the proof re-randomising integers α,β,γ,δ←$Zp4α,β,γ,δ←$Zp4, and then computes the proof components as follows:
πV1=(αV20+βW20−r21G2+αV21+βW21)∈G21×2,πW1=(γV20+δW20−s21G2+γV21+δW21)∈G21×2,πV2=(−αV10−γW10−αV11−γW11)∈G12×1,πW2=(−βV10−δW10−βV11−δW11)∈G12×1.πV1=(αV20+βW20−r21G2+αV21+βW21)∈G21×2,πW1=(γV20+δW20−s21G2+γV21+δW21)∈G21×2,πV2=(−αV10−γW10−αV11−γW11)∈G12×1,πW2=(−βV10−δW10−βV11−δW11)∈G12×1.
To show the above proof is valid, for the left-hand side (LHS) of the verification equation, we have:
LHS=E((1G1H(m)),(1G2vk))+E((r21V10+s21V11σ+r21W10+s21W11),(1G2−G2))=(e(1G1,1G2)e(1G1,vk)e(H(m),1G2)e(H(m),vk))+(e(r21V10+s21V11,1G2)e(r21V10+s21V11,−G2)e(σ+r21W10+s21W11,1G2)e(σ+r21W10+s21W11,−G2))=(1GT1GT1GTe(H(m),vk))+(1GT−r21e(V10,G2)−s21e(V11,G2)1GT−e(σ,G2)−r21e(W10,G2)−s21e(W11,G2))=e(H(m),vk)−r21e(V10,G2)−s21e(V11,G2)−e(σ,G2)−r21e(W10,G2)−s21e(W11,G2)LHS=E((1G1H(m)),(1G2vk))+E((r21V10+s21V11σ+r21W10+s21W11),(1G2−G2))=(e(1G1,1G2)e(H(m),1G2)e(1G1,vk)e(H(m),vk))+(e(r21V10+s21V11,1G2)e(σ+r21W10+s21W11,1G2)e(r21V10+s21V11,−G2)e(σ+r21W10+s21W11,−G2))=(1GT1GT1GTe(H(m),vk))+(1GT1GT−r21e(V10,G2)−s21e(V11,G2)−e(σ,G2)−r21e(W10,G2)−s21e(W11,G2))=e(H(m),vk)−r21e(V10,G2)−s21e(V11,G2)−e(σ,G2)−r21e(W10,G2)−s21e(W11,G2)
If the signature is a valid on message mm, then we have e(H(m),vk)+e(σ,−G2)=Te(H(m),vk)+e(σ,−G2)=T and we can write:
LHS=T−r21e(V10,G2)−s21e(V11,G2)−r21e(W10,G2)−s21e(W11,G2).LHS=T−r21e(V10,G2)−s21e(V11,G2)−r21e(W10,G2)−s21e(W11,G2).
On the other hand the RHS of the verification equation can be computed as follows:
RHS=E((V10V11),πV1)+E((W10W11),πW1)+E(πV2,(−V20V21))+E(πW2,(W20W21))=E((V10V11),(αV20+βW20−r21G2+αV21+βW21))+E((W10W11),(γV20+δW20−s21G2+γV21+δW21))+E((−αV10−γW10−αV11−γW11),(V20V21))+E((−βV10−δW10−βV11−δW11),(W20W21)).RHS=E((V10V11),πV1)+E((W10W11),πW1)+E(πV2,(−V20V21))+E(πW2,(W20W21))=E((V10V11),(αV20+βW20−r21G2+αV21+βW21))+E((W10W11),(γV20+δW20−s21G2+γV21+δW21))+E((−αV10−γW10−αV11−γW11),(V20V21))+E((−βV10−δW10−βV11−δW11),(W20W21)).
As we mentioned above, α,β,γ,δα,β,γ,δ are randomizing factors for the proof and for simplicity we assume they are all equal to 00. Thus we have:
E((V10V11),(1G2−r21G2))+E((W10W11),(1G2−s21G2))+E((1G11G1),(V20V21))+E((1G11G1),(W20W21))=−r21e(V10,G2)−s21e(V11,G2)−r21e(W10,G2)−s21e(W11,G2).E((V10V11),(1G2−r21G2))+E((W10W11),(1G2−s21G2))+E((1G11G1),(V20V21))+E((1G11G1),(W20W21))=−r21e(V10,G2)−s21e(V11,G2)−r21e(W10,G2)−s21e(W11,G2).
However, in below we show that even with the above random scalars, the left-hand side and right-hand side are equal. This means that the GS proof is complete. You can find more interesting examples in this blogpost [VKKM22].
E((V10V11),(αV20+βW20αV21+βW21))+E((W10W11),(γV20+δW20γV21+δW21))+E((−αV10−γW10−αV11−γW11),(V20V21))+E((−βV10−δW10−βV11−δW11),(W20W21))=(e(V10,αV20+βW20)e(V10,αV21+βW21)e(V11,αV20+βW20)e(V11,αV21+βW21))+(e(W10,γV20+δW20)e(W10,γV21+δW21)e(W11,γV20+δW20)e(W11,γV21+δW21))+(e(−αV10−γW10,V20)e(−αV10−γW10,V21)e(−αV11−γW11,V20)e(−αV11−γW11,V21))+(e(−βV10−δW10,W20)e(−βV10−δW10,W21)e(−βV11−δW11,W20)e(−βV11−δW11,W21))=(1GT1GT1GT1GT).E((V10V11),(αV20+βW20αV21+βW21))+E((W10W11),(γV20+δW20γV21+δW21))+E((−αV10−γW10−αV11−γW11),(V20V21))+E((−βV10−δW10−βV11−δW11),(W20W21))=(e(V10,αV20+βW20)e(V11,αV20+βW20)e(V10,αV21+βW21)e(V11,αV21+βW21))+(e(W10,γV20+δW20)e(W11,γV20+δW20)e(W10,γV21+δW21)e(W11,γV21+δW21))+(e(−αV10−γW10,V20)e(−αV11−γW11,V20)e(−αV10−γW10,V21)e(−αV11−γW11,V21))+(e(−βV10−δW10,W20)e(−βV11−δW11,W20)e(−βV10−δW10,W21)e(−βV11−δW11,W21))=(1GT1GT1GT1GT).
💡Note that GS proofs cannot prove the knowledge of a BLS signature with hidden messages as the prover needs to prove the pre-image of the hash function which is a non-linear operation.
Structure-preserving signatures and commitments [AFG+10] are primitives that are compatible with GS proof systems. It is an interesting area of research to explore more on efficient GS-friendly primitives like threshold primitives, for instance [CKP+22].
Performance Evaluation
We ran the prototype above on Ubuntu 22.04 with 16 GB RAM, an Intel Core i7-9850H CPU @ 2.60 GHz. The code is executed over the BN-254 curve in Charm-Crypto [AGM+13], and for our machine, it takes around 23 ms to compute a single pairing operation over this curve. The figures below show the required time to commit, prove, and verify a proof versus the number of variables in the PPE. During the commit and prove time, it is assumed that all variables are hidden and belong to the set of witnesses. The open-source implementation is available in this repository.
Applications of Groth-Sahai Proof Systems
Anonymous Credential Systems
Anonymous credential systems are used to allow a user to prove their identity to a verifier without revealing any sensitive information. The GS proof system can be used in anonymous credential systems to prove that a user possesses a certain credential (signature on lists of attributes) without revealing any information about the credential itself.
Electronic Cash Systems
Electronic cash systems allow a user to spend digital cash without revealing their identity (and are a subclass of anonymous credentials). The GS proof systems can be used in electronic cash systems to prove that the user possesses a digital coin without revealing any information about the coin itself. Electronic cash systems are useful in scenarios where privacy is important, such as online transactions.
Non-malleable Cryptographic Primitives
Many cryptographic primitives, including encryption, signature, and commitment schemes can exhibit malleability. A malleable scheme is one in which the primitive output can be modified by the adversary to still exhibit validity, possibly with respect to a related set of inputs. This is an undesirable characteristic in many scenarios. It was observed in several works [NY90, Sch01] that augmenting the output with a NIZK proof of its validity makes it non-malleable. It turns out many of these schemes have linear or pairing product structures, and thus can readily use GS NIZKs to instantiate the non-malleable version.
Structure-Preserving Cryptography
On the flip side, the efficiency of the GS proof system motivated the research community to design cryptographic primitives, like signatures, employing only linear and PPE equations over bilinear groups. In contrast to hash-based signatures, like BLS and RSA, these signatures are called structure-preserving signatures. It’s difficult to employ GS proofs for hash-based construction as verifying the hash itself is of high algebraic degree. A long line of works starting from [AFG+10] have significantly improved the efficiency and concrete security of SPS. More sophisticated schemes, like group and blind signatures, have also been made structure preserving and have enjoyed efficiency gains from GS proofs.
Related Work
The Schnorr proof system [Sch89], was the first ZK proof system for linear equations in group exponents. It was remarkably efficient, with proof size linear in the statement and witness sizes. One drawback was that it was in the Random Oracle model. The GS proof system was the first to achieve linear proof size in this setting using standard assumptions like DDH, in bilinear groups. The GS proof system inspired a long line of work leading to efficiency gains. The GS proof system has a universal CRS which works for any language. QA-NIZKs [JR13] obtained more efficient NIZKs in the setting where the CRS could be generated from the language. Subsequently, Libert et al. [LPJY14] achieved constant size QA-NIZKs, with later works [JR14, KW15] coming up with the shortest known NIZKs.
Final Thoughts
Groth-Sahai proofs have become an important tool in modern cryptography. They provide a way to prove the correctness of a statement without revealing any sensitive information. The GS proof system has a wide range of applications, including anonymous credential systems, electronic cash systems, e-voting, blind signatures, threshold issuance anonymous credentials and etc. As the field of cryptography continues to evolve, we can expect to see even more applications for the GS proof systems in the future.
Finally we stress that we did not discuss the security properties of GS proofs in this document. Volkov et al. in this blog post [VKKM22] has discussed these properties, and we suggest reading it as a complementary document. We would like to thank to Jens Groth and Daniel Slamanig for their helpful discussions and comments.
References
[AFG+10] Abe, Masayuki, Georg Fuchsbauer, Jens Groth, Kristiyan Haralambiev, and Miyako Ohkubo. “Structure-preserving signatures and commitments to group elements.”, Crypto’10.
[AGM+13] Akinyele, Joseph A., Christina Garman, Ian Miers, Matthew W. Pagano, Michael Rushanan, Matthew Green, and Aviel D. Rubin. “Charm: a framework for rapidly prototyping cryptosystems.” Journal of Cryptographic Engineering’13.
[BFM88] Blum, Manuel, Paul Feldman, and Silvio Micali. “Non-Interactive Zero-Knowledge and its applications.”, STOC’88.
[BLS01] Boneh, D., Lynn, B., Shacham, H., “Short signatures from the Weil pairing”. AsiaCrypt’01.
[EG14] Escala, Alex, and Jens Groth. “Fine-Tuning Groth-Sahai proofs.”, PKC’14.
[CKP+22] Crites, Elizabeth, Markulf Kohlweiss, Bart Preneel, Mahdi Sedaghat, and Daniel Slamanig. “Threshold Structure-Preserving Signatures.” Cryptology ePrint Archive (2022).
[GMR85] Goldwasser, Shafi, Silvio Micali, and Chales Rackoff. “The knowledge complexity of interactive proof-systems.”, STOC’85.
[Gro10] Jens Groth. “Short pairing-based non-interactive zero-knowledge arguments”. ASIACRYPT’10.
[Gro16] Groth, Jens. “On the size of pairing-based non-interactive arguments.”, Eurocrypt’16*.*
[GS08] Groth, J., Sahai, A., “Efficient Non-interactive Proof Systems for Bilinear Groups”. Eurocrypt’08.
[GW11] Gentry, Craig, and Daniel Wichs. “Separating succinct non-interactive arguments from all falsifiable assumptions.”, STOC’11.
[HHK+17] Herold, Gottfried, Max Hoffmann, Michael Klooß, Carla Ràfols, and Andy Rupp. “New techniques for structural batch verification in bilinear groups with applications to Groth-Sahai proofs.”, ACM CCS’17.
[JR13] Jutla, Charanjit S., and Arnab Roy. "Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces", Asiacrypt’13.
[JR14] Jutla, Charanjit S., and Arnab Roy. “Switching lemma for bilinear tests and constant-size NIZK proofs for linear subspaces.”, Crypto’14.
[KW15] Kiltz, Eike, and Hoeteck Wee. "Quasi-adaptive NIZK for linear subspaces revisited", Eurocrypt’15.
[LPJY14] Libert, Benoît, Thomas Peters, Marc Joye, and Moti Yung. "Non-malleability from malleability: Simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures", Eurocrypt’14.
[NY90] Naor, Moni, and Moti Yung. "Public-key cryptosystems provably secure against chosen ciphertext attacks", STOC’90.
[Ped91] Pedersen, Torben Pryds. “Non-interactive and information-theoretic secure verifiable secret sharing.”, Crypto’91.
[Sah01] Sahai, Amit. “Simulation-sound non-interactive zero knowledge”, 2001
[Sch89] Schnorr, C.P.: “Efficient identification and signatures for smart cards.”, Crypto’89.
[Tom22] Tomescu, A., “Pairings or Bilinear maps.” https://alinush.github.io/2022/12/31/pairings-or-bilinear-maps.html.
[VKKM22] Mikhail Volkhov, Dimitris Kolonelos, Dmitry Khovratovich, Mary Maller, “Groth-Sahai Proofs Are Not That Scary”, June 6, 2022. https://crypto.ethereum.org/blog/groth-sahai-blogpost.
Blog
