Elliptic Curve Pairings
At Statebox we are exploring using boolean circuits to model computation. One thing we’d like to do is verify correct computation on a blockchain in a scalable way. A zero-knowledge proof system, like a zkSNARK, can do this. In my last post I explained how to create a zkSNARK that verifies a boolean circuit in Libsnark.
In this post, I’d like to take a closer look at the core bit of mathematics that makes a zkSNARK work: the elliptic curve pairing.
Introduction
Usually in cryptography we want our encryption functions to destroy as much information as possible. The inputs to these functions should appear to be completely unrelated to their outputs — unless, of course, you know the key.
However there are situations where we might want a little bit of information about the inputs to be recoverable, but not all of it.
For instance, suppose you had an online store and you wanted to check that your customer’s password was sufficiently complex without asking the user to actually reveal their password to you. First they would encrypt their password using some encryption function. Then you would need to be able to tell from only the encrypted output that the input to the function satisfied some condition.
This is possible. It requires a form of encryption that doesn’t destroy all information about its inputs. One mathematical object used to accomplish this is an elliptic curve pairing.
Elliptic Curve 101
A lot of this information can be found elsewhere, so I’ll just give the bare necessities. An elliptic curve is a polynomial that looks like:
The set of points (x,y) that are solutions to this equation plus a “point at infinity” form a group under a special addition rule.
Two points are added on elliptic curves by drawing a line through the two points. Because the curve is degree three this line will intercept the curve in a third place. That point of intersection is then reflected over the x-axis. Because of the y-squared term on the left side the curve is symmetric over the x-axis and this reflected point is also on the curve. The reflected point is the sum.
The geometric method of adding points is beautiful, but not so practical. There is a function that computes the sum of two points using on a curve by using their coordinates. Thankfully, this function is a rational function which is not too hard to compute. A point can also be doubled using a similar rational function. A double-and-add algorithm makes it practical to compute arbitrary multiples of an elliptic curve point, which I will write as n*g for integer n and some elliptic curve point g.
The point at infinity serves as the identity of the group. Two elliptic curve points that lie on the same vertical line are inverses.
Since addition and doubling are computed by rational functions on the coordinates, an elliptic curve group can be created using coordinates from any field. In a cryptographic setting we would use a finite field for the coordinates. Using a finite field destroys the nice geometric method of adding points by drawing lines between points, but the rational functions that compute adding and doubling are the same.
The Elliptic Curve Discrete Logarithm Problem
Something that is believed to be very hard to do with elliptic curve points is to compute the elliptic curve discrete logarithm (ECDLP). Given a point g on an elliptic curve and some multiple of that point n*g, what is n?
One of the most efficient algorithms for solving ECDLP, the baby-step giant-step method, runs in time exponential on the number of digits in the order of the elliptic curve group. For large groups this problem is highly impractical to solve.
Since this is problem is difficult, we can choose a secret n and be sure that it will remain secret even if we reveal g and n*g.
Why is it called discrete logarithm? Usually this problem is expressed in multiplicative notation, where the problem becomes computing n from g and g^n, essentially computing the base-g logarithm of g^n.
The Torsion Subgroup
An r-torsion subgroup is a subgroup formed of all elements g for which r*g = 0. The torsion subgroups of elliptic curve groups have a predictable structure. If we say E[r] is the the r-torsion subgroup of elliptic curve group E, then E[r] has this structure:
The caveats are that r must be relatively prime to the degree of the field E is defined on, and we may have to pass up to an extension of that field in order to get “all” of the points in E[r].
The Embedding Degree
The embedding degree k is the smallest degree field extension needed to get the entire torsion subgroup E[r].
The embedding degree k, as well as r, have an enormous effect on the security and efficiency of an elliptic curve and its pairing.
Elliptic Curve Pairings
An elliptic curve pairing is a function that takes a pair of points on an elliptic curve and returns an element of some other group, called the target group. Elliptic curve pairings have this nice essential property:
For some g1, g2, and g3 on the curve and integers a and b.
This is called bilinearity since the pairing is linear in both coordinates.
A pairing needs to have a further property, called non-degeneracy. For generators g1, g2:
The groups G1 and G2 are often different subgroups of a torsion group E[r], and the target group is either the rth roots of unity or a cyclic group isomorphic to it.
An Attack on Elliptic Curve Cryptography
Elliptic curve pairings were introduced by French mathematician André Weil in 1940 as a tool for solving an analogue of the Riemann Hypothesis for finite fields.
Pairings were later used as an attack on elliptic curve cryptography. A desirable property of a secure cryptosystem is that the Decisional Diffie-Hellman problem (DDH) is difficult in the underlying group. The DDH problem is this: given g, x*g, y*g, can you tell the difference between xy*g and a randomly chosen z*g? If that is difficult, the group has DDH. A group that where DDH holds can be used to hide the fact that the coefficients x, y and xy are related by multiplication.
The bilinearity property of pairings can be used to break DDH. (How? Compute e(x*g, y*g) and e(g, z*g). If they are equal, then xy = z with high probability.)
Since pairings can break DDH, a pairing can reveal that secret values are related by multiplication even though the values themselves remain secret.
Pairings are only able to show a relationship with one single multiplication. One would need a three-coordinate, trilinear function to reveal a relationship with two multiplications.
How are Pairings used in zk-SNARKs?
Pairings can reveal that secret values are related by addition and up to one multiplication.
If a statement can be transformed into a relationship with a single multiplication than it can easily be checked using a pairing. For example, suppose I want to convince you that I have an integer solution to a quadratic equation but I don’t want to reveal it. Here is an example equation:
I take my root a and a pair of elliptic curve points g1 and g2. I compute a*g1 and a*g2 give you the results, along with the points g1 and g2. Because of the ECDLP I can be sure you won’t be able to compute a and my root will remain a secret.
You use a pairing and compute:
By the bilinearity property, this is equal to:
If this is equal to 1, then a^2-2027a+16152 is equal to 0 with high probability. (The non-degeneracy condition, along with a large target group ensures this.) I have convinced you that my secret a really is a solution to the quadratic equation without ever revealing it.
In a zk-SNARK, elliptic curve pairings are used to check a system of quadratic constraints like the one above. The system of constraints is converted into a single large polynomial that has particular roots only if each of the quadratic constraints is satisfied.
Computing a Pairing
The best known algorithm for computing pairings is Miller’s algorithm. The algorithm is computationally expensive, as its complexity is polynomial on the order of the particular subgroup used in the pairing. For security, the order of this subgroup is very large, so the algorithm can take some time.
For this reason, efficient zero-knowledge protocols using elliptic curve pairings minimize the amount of pairing values that must be computed. The Pinocchio Protocol in PGHR13 needs 11 pairing values, while Groth16 needs only 3.
Want to know more about pairings?
The introductory sources on elliptic curve pairings on the internet are slim, but I found these helpful and illuminating:
Vitalik Buterin’s blog post:
https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
Craig Costello’s Pairings for Beginners:
http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf
This talk by Dan Boneh:
https://www.youtube.com/watch?v=8WDOpzxpnTE
