# Elliptic curves We’ll need to brush up on some maths here, and we’ll start from a definition: the set of points (X,Y) that satisfies the equation y^2 = x^3 + A*x + B is an elliptic curve

Prof. Google offers a lot of information about these curves, and some simple drawings that help to visualize their shapes; these pictures will typically show a continuous line, while our curves will be made of separated points, as we operate on finite fields and not on the real numbers, but ok: we’ll remember to wrap the curve at the edges and just use “a few” points of that wrapped line. We’ll be using elliptic curves to define robust, collision resistant one-way functions, so X, Y, A, B will have all to be in a finite field (0, 1, 2, 3, …, p-1), and p needs to be a prime number > 3 (for our needs, p will be a large number).

The theory of elliptic curve is vast and complex; not all A and B can be used, and depending on how we choose them, we might weaken the hardness of the one-way function that we are building. Facts of the matter is that a lot of research has been made on elliptic curves, and some specific family of curves (defined by particular choices of the A and/or B coefficients) were identified and are now used. For our little introduction here, it’s enough to know that for our one-way function we’ll use curves that are robust, and that are pairing-friendly, we’ll see what that means later.

Again, we want to implement with our chosen elliptic curve, a one-way function that offers “homomorphic hiding”; we then need to define a mapping between our original finite field and a new space, and we also need to define operators on the new space that will respect the algebraic structure of the original field. Our new space will be defined as follows:

We pick a point g=(x1,y1) that satisfies the elliptic curve. We define what "0" is in this space, and then a way to calculate the points 2*g, 3*g, 4*g, … such that all the calculated points belong to the elliptic curve, and that for a set r, the point r*g=0, and (r+1)*g=g. We have built a cyclic group!

The above operations are implemented in the following way: sum of a point p to itself is calculated by identifying where the tangent line in p intersects another point of the curve: the result point will be that one, with opposite sign on the y coordinate. A similar process defines the sum of two different points: instead of the tangent line, we’ll use the line that connects the two points to be added. That line intercepts the curve in a third point: by changing the sign of its y coordinate we get our result. “1” is the point g, “0” is when the point goes to infinite, e.g. if for a point p, we do p - p, the two points have the same x coordinate, the line that connects them is parallel to the y axis, the line does not intercept another point of the curve and goes to infinite, i.e. 0.

With this just defined addition operator, we can calculate g + g = 2*g (tangent on the point g), 2*g + g = 3*g (line between the point 2*g and the point g), 3*g + g = 4*g and so on. On the Internet you can find some cool graphic representation of this process. This set of points, that both belong to the elliptic curves and whose coordinates are elements of the finite field, is our hidden space. We can map each field element to a point on the curve with the following mapping: p = hh(k)= k * g, and that has all the good properties that we need for our homomorphic hidings: if the elliptic curve was chosen well, the only way to calculate k by only knowing p and g is via brute force attempts. This mapping is also addition homomorphic, so (a+b) -> (a+b)*g = a*g + b*g

By the way, Bitcoin uses the elliptic curve y² = x³+7, on the finite field (0, 1, .., 2256–232-978) for assigning key pairs: if k, a field element, is the private key of an address, then p=k*g is its public address. But… forget Bitcoin: we are using elliptic curves in a much more sophisticated way...