Pairings on Twisted Edwards Curves

[HarryR]

The following papers cover this:

• A note on twists for pairing friendly curves *https://crypto.stackexchange.com/questions/48236/pairing-on-fourq
• https://www.semanticscholar.org/paper/Another-approach-to-pairing-computation-in-Edwards-Ionica-Joux/d4539b7421ecf58e619d622637e506e67d761140 - Another approach to pairing computation in Edwards coordinates.pdf
• https://www.semanticscholar.org/paper/Pairing-computation-on-Edwards-curves-with-twists-Li-Wu/50a4df4c7a69341284e87821d95785af4b4ccd4b - 2012-532.pdf
• https://www.semanticscholar.org/paper/Improved-Miller%E2%80%99s-Algorithm-for-Computing-Pairings-Le-Tan/581c57d0e7e8fd972c0c62b95c576ddcbe6f2c66
• https://www.semanticscholar.org/paper/Faster-Computation-of-the-Tate-Pairing-Arene-Lange/4efef427065952f88c6d74a3dd9d3ea6af60922f - 2009-155.pdf
• https://www.semanticscholar.org/paper/Further-refinements-of-Miller%E2%80%99s-algorithm-on-curves-Le/c2659bc24ae9ed30292562e3a56610e6fc0c4fc0 - 1305.2694.pdf
• https://www.semanticscholar.org/paper/Faster-Pairing-Computation-Arene-Lange/856d82207024845f4daca812da47387f7c172e99 - edpairing.pdf
• https://www.semanticscholar.org/paper/Faster-Pairing-Computations-on-Curves-with-Twists-Costello-Lange/3d7eeba95b372a66df2cd6b61ca3dd4b8106b9e2
• https://link.springer.com/chapter/10.1007/978-3-642-11925-5_8
• https://www.semanticscholar.org/paper/Refinement-of-Miller's-Algorithm-Over-Edwards-Xu-Lin/b994f6b61178a9d55d96ed800cdc7d0bedd1609e
• https://cryptosith.org/michael/data/thesis/2009-05-13-diss.pdf Chapter 4 (Pairings on Edwards curves)
• https://eprint.iacr.org/2018/969 - code: http://www.martindale.info/research/TNFS-secure-pairing-implementations/ - 2018-969.pdf

Faster Pairing Computations on Curves with High-Degree Twists.pdf pairings_lange.pdf TransComp2013.pdf

Slideshow:

• 2009-05-05-Essen.pdf
• Exponentiating in Pairing Groups

  • Michael Naehrig

[HarryR]

From Faster Computation of the Tate Pairing:

From Theorem 1 (§4,pg6)

Solving the linear system, we get the projective solution

• c_Z2 = X_1 * (Y_1 + 1) * (1 - Y_1)
• c_XY = (Y_1 + 1) * ((d * X_1^2 * Y_1) - 1)
• c_XZ = (Y1 + 1) * (Y_1 - (a * X_1^2))

Let P_1 and P_2 be two affine K-rational points on the twisted Edwards curve E_{a,d}, and let P_3 = (X_3 : Y_3 : Z_3) = P_1 + P_2 be their sum. Let

• l_1 = (Z_3 * Y) - (Y_3*Z)
• l_2 = X

be the polynomials of the horizontal line L_{1,P_3} through P_3 and the vertical line L_{2,O} through O respectively and let

• φ = c_{z^2} * (Z^2 + YZ) + {c_XY}^XY + {c_XZ}^XZ be the unique polynomial (up to multiplication by a scalar) defined by Theorem 1.

---

What is undefined at this point is:

• k (embedding degree)
• F_{p^k} = F_{p^{k/2}} * α
• K_2, where K is a field (which we can't choose... the existing BabyJubJub field)
• α = in a quadratic extension K_2 of K.
• δ = α^2 ∈ F_{p^{k/2}}
• The map ε : (x,y) → (αx, y) defines a K_2-isomorphism between the twisted edwards curves E_{aδ,dδ} and E_{a,d}, hence the map ε is the prototype of a quadratic twist.

---

TODO:

• Derive α from p and k where p^k = p^(k/2) * α
• δ = α*α ∈ F_{p^{k/2}}

The problem is it's looking unlikely that we can find parameters which allow pairings on the existing Baby JubJub curve.

[HarryR]

From the example code referenced by the paper Optimal TNFS-secure pairings on elliptic curves with even embedding degree:

// --------------------------------------------------------------------
//
//  File:        TAk12D3.rtf [Twisted Ate pairing for twisted Edwards curves with sextic twists]
//  Date:        Oct. 10, 2018
//  Last update: Oct. 10, 2018
//  Description: Magma implementation of the twisted ate pairing on twisted Edwards curves with sextic twists.
//               Embedding degree k = 12, CM discriminant D = 3
//
//  (c) 2018, Georgios Fotiadis & Chloe Martindale
//                 
//  Georgios Fotiadis, University of the Aegean, Greece, email: [email protected]
//  Chloe Martindale, Technische Universiteit Eindhoven, the Netherlands, email: [email protected]
// --------------------------------------------------------------------
//  Polynomial Family
//  p(x) = (x^6 − 2*x^5 + 2*x^3 + x + 1)/3
//  t(x) = x + 1
//  r(x) = x^4 - x^2 + 1
// --------------------------------------------------------------------
//  Twisted ate pairing: a(P,Q) = [ f_{T2,P}(Q) ]^((p^k - 1)/q)
// --------------------------------------------------------------------

//Weierstrass to Montgomery
MontPoint:=function(P, alpha, s)
  x:=s*(P[1] - alpha);
  y:=s*P[2];
  MP:=Vector(2,[x,y]);
  return MP;
end function;

//Montgomery to Edwards
EdPoint:=function(P)
  X:=(P[1]/P[2]);
  Y:=(P[1] - 1)/(P[1] + 1);
  Z:= 1 ;
  W:=(X*Y)/Z;
  EP:=Vector(4,[X,Y,W,Z]);
  return EP;
end function;

//Miller's function point doubling: h_{P,P}(Q) 
hDBL:=function(P, Eda, Edd, eta, theta)
  X1:=P[1]; Y1:=P[2]; W1:=P[3]; Z1:=P[4];
  A:=X1^2;
  B:=Y1^2;
  C:=Z1^2;
  D:=Eda*A;
  E:=B + D;
  F:=2*C - E;
  G:=(X1 + Y1)^2 - A - B;
  H:=(Y1 + Z1)^2 - B - C;
  X3:=G*F;
  Y3:=E*(B - D);
  Z3:=E*F;
  W3:=G*(B - D);
  CX:=H - 2*D;
  CY:=(X1 + Z1)^2 - A - C - G;
  CW:=Edd*((X1 + W1)^2 - A) - C - E;
  R:=Vector(4,[X3,Y3,W3,Z3]); 
  h:=CX*eta + CW*theta + CY;
  return R, h;
end function;

//Miller's function point addition h_{P,S}(Q) 
hADD:=function(P, S, Eda, Edd, eta, theta)
  X1:=P[1]; Y1:=P[2]; W1:=P[3]; Z1:=P[4];
  X2:=S[1]; Y2:=S[2]; W2:=S[3]; Z2:=S[4];
  A:=X1*X2;
  B:=Y1*Y2;
  C:=Z1*W2;
  D:=Z2*W1;
  E:=W1*W2;
  F:=(X1 - Y1)*(X2 + Y2) - A + B;
  G:=B + Eda*A;
  H:=D - C;
  I:=D + C;
  X3:=I*F;
  Y3:=G*H;
  Z3:=F*G;
  W3:=I*H;
  CX:=(W1 - Y1)*(W2 + Y2) - E + B + H;
  CW:=X2*Z1 - X1*Z2 - F;
  CY:=(X1 - W1)*(X2 + W2) - A + E;
  R:=Vector(4,[X3,Y3,W3,Z3]); 
  h:=CX*eta + CW*theta + CY;
  return R, h;
end function;

//final exponentiation k = 12, D = 3
finalexp:=function(f, x0, p, q, Fp)
  t0:=1;
  f:=Frobenius(f, Fp, 6)/f; 
  f:=Frobenius(f, Fp, 2)*f; 
  x1:=x0^2;
  l:=((x1 - 2*x0 + 1) div 3);
  y:=f^l;
  t:=Frobenius(y, Fp, 3);
  t0:=t0*t;
  t:=Frobenius(y^x0, Fp, 2);
  t0:=t0*t;
  y:=y^(x1 - 1);
  t:=Frobenius(y, Fp, 1);
  y:=y^x0;
  t0:=t0*t*y*f;
  return t0;
end function; 

//Twisted ate pairing calculation
TwistedAatePairing:=function(P, Te, q, Eda, Edd, p, k, z0, eta, theta, Fp)
  f:=1;
  T:=P;
  i:=Floor(Log(2,Te)) - 1; 
  s:=Intseq(Te,2); 
  while i ge 0 do
    T,h:=hDBL(T, Eda, Edd, eta, theta); 
    f:=h*f^2; 
    if s[i+1] eq 1 then
      T,h:=hADD(P, T, Eda, Edd, eta, theta); 
      f:=h*f; 
    end if;
    i:=i - 1;
  end while;
  f:=finalexp(f, z0, p, q, Fp);
  return f;
end function;

//MAIN PROGRAM
t2:=0; LOOP:= 100 ;
D := 3 ; k := 12 ;                 
p := 13134002065465082451978965994689008063352936155273231976285809101659121364125466002052917860807951110122803152950817 ;              
q := 115792089237317700346157840501962347976585376275497230292808382329089323460673 ;      
h := 113427455640313558237160070382243949568 ;    
z0:= 18446744073709611553 ; 
a:= 0 ; 
b:= 1 ;

s:=k div 6;
Fp := GF(p);
P<x> := PolynomialRing(Fp);

E:=EllipticCurve([Fp!(a), Fp!(b)]); 
f:=x^3 + a*x + b; 
n:=h*q; 
t:=p + 1 - n; 
T:= t - 1; 
Te:=T^2 mod q;

ROOTS:=Roots(f);
ALPHA:=Vector(3,[ ROOTS[1][1],ROOTS[2][1],ROOTS[3][1] ]);

for i:= 1 to 3 do
  test,sqrt:=IsSquare(1/(3*ALPHA[i]^2 + a));
  if (test eq true) then
    ss:=sqrt;
    alpha:=ALPHA[i];  
    break i;
  end if;
end for;

//Montgomery Curve
A:=Fp!(3*alpha*ss); 
B:=Fp!(ss);
//Twisted Edwards Curve
Eda:=Fp!((A + 2)/B); 
Edd:=Fp!((A - 2)/B); 

M:=Fp!(2*(Eda + Edd)/(Eda - Edd)); 
N:=Fp!(4/(Eda - Edd)); 

P<z> := PolynomialRing(Fp);
g:=IrreduciblePolynomial(Fp,s); 
Fps<u> := ExtensionField<Fp,z|g>;
R<zz> := PolynomialRing(Fps);

for i1:= 1 to 5 do
  for i0:= 0 to 5 do
    fX:=i1*u + i0; 
    FX:=zz^(k div s) - fX;
    if IsIrreducible(FX) eq true then
      Fpk<v> := ExtensionField<Fps,zz|FX>; 
      x0:=Roots(FX, Fpk); 
      w:=x0[1][1];
      break i1;
    end if;
  end for;
end for;

W:=w; 
bt:=(-M^3*N^3)/(27*W^6);
Et := EllipticCurve([Fps!(0),Fps!(bt)]);
ht:=#Et div q; 
if IsZero(#Et mod q) eq false then
  W:=w^5; 
  bt:=(-M^3*N^3)/(27*W^6);
  Et := EllipticCurve([Fps!(0),Fps!(bt)]); 
  ht:=#Et div q; 
end if;

bk:=Fpk!((-M^3*N^3)/(27));
Ek:=EllipticCurve([Fpk!(a), Fpk!(bk)]); 
Zk<xx> := PolynomialRing(Integers());
NN := Resultant(xx^k - 1, xx^2 - t*xx + p);
hk := NN div q^2;

for i:= 1 to LOOP do
//create two points PW and Pa in E(Fp) of order q (two points because of the bilinearity check)
G:=Random(E); 
nP:=h; 
P:=nP*G; 
Pa:=P;                               
nP:=Random(1, q - 1); 
PW:=nP*P;   

MP:=MontPoint(PW, alpha, ss);
EP:=EdPoint(MP);
MPa:=MontPoint(Pa, alpha, ss);
EPa:=EdPoint(MPa);

//create two points QW and Qa in Et(Fp^2) of order q (two points because of the bilinearity check)
G:=Random(Et); nQ:= ht ; 
Q:=nQ*G;  
QW:=Q; 
xQ:=QW[1]*W^(2); 
yQ:=QW[2]*W^(3); 
E1:=Ek![xQ,yQ]; 

XQ:=Frobenius(xQ, Fp, 1); 
YQ:=Frobenius(yQ, Fp, 1); 
D1:=Ek![XQ,YQ]; 
QW:=D1-E1; 

xQ:=QW[1]*W^(-2);
yQ:=QW[2]*W^(-3);
QW:=Et![xQ,yQ]; 

nQ:=Random(1, q - 1); 
Qa:=QW; 
QW:=nQ*QW; 

eta:=N*(3*QW[1]*W^2 + 3*N - M*N)/(6*W^3*QW[2]);
theta:=N*(3*QW[1]*W^2 - 3*N - M*N)/(6*W^3*QW[2]);
etaa:=N*(3*Qa[1]*W^2 + 3*N - M*N)/(6*W^3*Qa[2]);
thetaa:=N*(3*Qa[1]*W^2 - 3*N - M*N)/(6*W^3*Qa[2]);
nPQ:=nP*nQ;

t1 := Cputime();
twistedate:=TwistedAatePairing(EP, Te, q, Eda, Edd, p, k, z0, eta, theta, Fp);
t2:=t2 + Cputime(t1); 
end for;
t2:=t2/LOOP;
printf"average time for %o pairings = %o\n", LOOP, t2;

//Bilinearity check
TwistedAatePairing(EP, Te, q, Eda, Edd, p, k, z0, eta, theta, Fp) eq TwistedAatePairing(EPa, Te, q, Eda, Edd, p, k, z0, etaa, thetaa, Fp)^(nPQ);

[HarryR]

For pairing computation to be efficient within the zkSNARK circuit the extension fields need to be computable using the base field.

From https://eprint.iacr.org/2008/292.pdf § pg 9 - 4.1 The case of an even embedding degree

Koblitz and Menezes showed in 21 that if q and k are chosen such as q ≡ 1 ((mod ) 12) and k = 2^i 3^j, then the arithmetic of the extension field F_{q^k} can be implemented very efficiently as this field can be built up as a tower of extension fields:

From 21 § 5 pg 9 Theorem 2

Let F_{p^k} be a pairing-friendly field, and let β be an element of F_p that is neither a square nor a cube in F_{p·^3} Then the polynomial X^k − β is irreducible over F_p.

Taken from: https://www.hindawi.com/journals/mpe/2013/136767/ §2.1 Tate Pairing

Given that the base field is fixed, we need to find pairing friendly curves which:

• p > 3 where p is a prime`
• Let F_q be a finite field with q = p^n
• q = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001
• Let k > 1 denote the embedding degree with respect to r
• that is k is the smallest positive integer such that r | q^k - 1
• r is prime such that r | #E(F_q)

Say we start with the BabyJubJub curve we're currently using.

• #E(F_q) = 21888242871839275222246405745257275088614511777268538073601725287587578984328
• r = 2736030358979909402780800718157159386076813972158567259200215660948447373041
• #E(F_q) = 2^3 * r

Unfortunately the embedding degree k will be too high.

[HarryR]

https://github.com/zcash/zcash/issues/3425 https://github.com/matter-labs/Groth16BatchVerifier/blob/master/BatchedGroth16.md https://github.com/zcash/zcash/issues/3924

[daira]

The only currently-known ways to construct a new pairing-friendly curve of given arbitrary order, are Cocks–Pinch and Dupont–Enge–Morain, which are described in sections 4.1 and 4.2 of Freeman 2006. These will produce curves with ρ ≈ 2, i.e. with G₁ field size roughly twice the given order.

[daira]

Is there a reason you can't use the E_BLS and E_CP curves described in section 8 of the Zexe paper?

[HarryR]

The big thing holding me back at the moment is Ethereum compatibility, Ethereum doesn't have pairing operations available for any curve other than (alt)bn128.

I have come to the realisation that I need to just accept that as a reality, and instead focus on things which use these pre-discovered curves rather than searching for a potentially impossible result.

[stefandeml]

yeah, I think we have to live with the fact that the current curve we have on Ethereum( bn128) works on a field with low 2-adicity. Hence the construction used in Zexe (Cocks–Pinch) can't be applied based on my understanding.

[amakerofbonnetsandhoods]

In addition to @stefandeml 's point, cocks-pinch curves have a composite order, so you cannot build a cycle but only a chain of pairing-friendly curves. Here in section 7 it is proved that composite-order cycles do not exist.

[HarryR]

@amakerofbonnetsandhoods a chain of pairing-friendly curves is good enough.

Even one sub-level would allow for aggregate anonymous transactions, where each transaction is a zkSNARK proof using a pairing friendly sub-curve, rather than just aggregate transactions we have now.

Of course, full recursion is an ideal which enables so much more, but a good compromise is just to be able to verify many other zkSNARKs within one - this provides an awesome building block for computational compression and opens up so many opportunities.

[amakerofbonnetsandhoods]

@HarryR that is true. Did you or anyone implement a verifier circuit over zexe cock-pinch curve ?

[HarryR]

zexe implements in-circuit pairing operations at:

• https://github.com/scipr-lab/zexe/blob/master/snark-gadgets/src/pairing/bls12/mod.rs
• https://github.com/scipr-lab/zexe/blob/master/snark-gadgets/src/groups/curves/short_weierstrass/bls12/mod.rs
• https://github.com/scipr-lab/zexe/blob/master/dpc/src/gadgets/verifier/gm17.rs

etc.