1
$\begingroup$

I am trying to understand ABE for a project of mine. I've grasped the concept of elliptic curves, but could not understand the meaning of divisors for functions on them.

Could anyone help me with this? I mean, why would we want to define functions on an elliptic? What is the benefit?

$\endgroup$
  • 1
    $\begingroup$ Divisors are used to keep track of zeros and poles of rational functions. For example, the divisor associated to the function $\frac{X - xZ}{Z}$ is $\langle P \rangle + \langle -P\rangle - 2\langle\mathcal{O}\rangle$ where $P = (x,y)$ and $\mathcal{O}$ is the point at infinity. $\endgroup$ – user94293 Feb 5 '18 at 2:58
  • $\begingroup$ Thank you for answering. In fact, I do not know why we define divisor. For example, in your example: you discussed (X-xZ)/Z. So, in elliptic curve, I mean y2=x3+ax+b, we just have x and y. Why did you discuss Z? What is Z?! $\endgroup$ – tesoke Feb 5 '18 at 4:12
  • $\begingroup$ Working with projective coordinates, $Y^2 Z = X^3 + aXZ^2 + bZ^3$, you can see that point $P = (x:y:1)$ and $\mathcal{O} = (0:1:0)$. Hence (i) $X - xZ = 0$ for $P = (x:y:1)$ and $-P=(x:-y:1)$, and (ii) $Z = 0$ for $\mathcal{O}$ (with multiplicity 2). $\endgroup$ – user94293 Feb 5 '18 at 5:29
  • $\begingroup$ See also crypto.stanford.edu/pbc/notes/elliptic/divisor.html $\endgroup$ – user94293 Feb 5 '18 at 5:42
1
$\begingroup$

As @user94293 mentioned, divisors are a way to keep track of the zeroes and poles of a function. (Poles are related to projective coordinates).

Think of a function like $f(x) = x^2 - x + 6$. It has two zeroes: $-2$ and $3$. If I only gave you these two zeroes, you would be able to recreate the original function, up to a constant factor.

The reason divisors are used in pairing-based cryptography (and thus in ABE) is because the pairing function itself is defined as the function which has a particular divisor. This is enough since, as mentioned, if you have the divisor (and thus the zeroes), you can reconstruct the function.

In particular, the Tate pairing is defined as the function $\tau_r(P, Q) = f_\tau(Q)^{(q^k-1)/r}$ where $f_\tau$ is a rational function (a function which is the ration of two functions) with divisor $r\langle P \rangle - r\langle \infty \rangle$, which means it has $r$ zeroes in point $P$ and $r$ poles in the point at infinity. This function is computed with Miller's algorithm.

In short, divisors are used to specify the pairing function used in pairing-based cryptography.

$\endgroup$
  • $\begingroup$ Thank you so much. This explanation about the reason to try using divisors was good. I want to read again the chapter of the book about the paring based with this new viewpoint. I will ask you again if I have another problem. Thanks again. $\endgroup$ – tesoke Feb 5 '18 at 17:00
1
$\begingroup$

The notion of a divisor is defined over a (general) smooth algebraic curve and elliptic curves are smooth algebraic curves (I suggest you to read a book in algebraic curves to grasp this notion e.g. Fulton's book). A divisor over a (smooth) curve is just a typical sum of the form $n_1P_1+n_2P_2+\cdots +n_kP_k,$ where $P_i$ are projective points of the curve (so some $P_i$'s may be points at infinity) and $n_i$ are integers. The sum of all $n_i$'s is called degree of the divisor. Say, for instance that we have the curve $E:y^2=x^3+3x.$ Then, $D=n(1,2),$ for some $n\in {\mathbb{Z}},$ is a divisor over $E$ of degree $n.$ Now, there are some divisors that corresponds to rational functions of curves. These divisors always have degree $0$ (this is a consequence of Bezout theorem).

In general divisors are needed when you want to construct a function having specific poles. There is a very deep theorem in algebraic geometry which is called Riemann-Roch theorem that describes the set of functions having prescribed poles (equivalently specific divisor).

A poster, previous suggested the function $f(x,y)=x-a$ (equivalently we can write the previous function as $f(X,Y,Z)=\frac{X-aZ}{Z}$) where $P=(a,b)$ is a point of an elliptic curve of the form $y^2=x^3+Ax+B$. Then, the divisor that corresponds to this function is $div(f)=P + Q - 2\infty.$ In other words $f$ has a simple zero at $P=(a,b)$ and $Q=(a,-b)$ (and so has a double pole at infinity). Indeed, since $f(P)=f(Q)=0$ and there are not any other roots.

Having in mind that rational functions and the divisors that correspond to them, is in fact equivalent notions, I think you can avoid the technical language of divisors in elliptic curves as used in cryptography.

EDIT. To understand divisors you have to understand what the projective model of a curve is. Say $F(x,y)=x^2-y^2-1=0$ the equation of an algebraic curve. To get the projective model you have to "insert" a new variable say $Z,$ and homogenize polynomial $F.$ So the projective equation of the curve is $F^*(X,Y,Z)=X^2-Y^2-Z^2=0.$ Now setting $Z=0$ you get the points at infinity of the curve, in this case there are only two $(X,Y,Z)=(1,1,0),(1,-1,0)$ (in projective plane colinear points "considered" as one point. So the point $(X,\pm X,0)\equiv (1,\pm 1,0)$ ).

$\endgroup$
  • $\begingroup$ Thank you for your explanation. But there is a vague part for me in your comment: I could not understand yet that why we discuss Z! I say that we discuss elliptic curve in a plane in X-Y coordinates, so what is Z? Z is a coordinate when we discuss volume not plane. When you exemplify a function with point P=(a,b), this is a line, but I cannot see f=(X-az)/Z as a formula for this line! $\endgroup$ – tesoke Feb 6 '18 at 23:57
  • $\begingroup$ Thank you. A quick question: how did you conclude X2−Y2−Z2=0 from x2−y2−1=0? I mean what is the rule for construction projection model of x2−y2−1=0? $\endgroup$ – tesoke Feb 7 '18 at 0:20
  • $\begingroup$ homogenize with respect to the new variable $Z.$ Say $F(x,y)$ a polynomial, to get the homogeneous polynomial $F^*(X,Y,Z)=Z^dF(X/Z,Y/Z)$ where $d=\deg F.$ $\endgroup$ – 111 Feb 7 '18 at 0:25
  • $\begingroup$ Thank you so much. I got this. But in your previous explanation, you said that for getting poles, we should set Z=0. So for F∗(X,Y,Z)=X2−Y2−Z2=0, we will have four poles: (1, 1, 0) and (1, -1, 0) and (-1, 1, 0) and (-1, -1, 0). Why you said just two pints: (X,±X,0)≡(1,±1,0)? $\endgroup$ – tesoke Feb 7 '18 at 0:32
  • $\begingroup$ Not easy to explain in a small comment. But $(X,X,0)=(1,1,0)=(2,2,0)=...$ In fact the projective plane is the real plane with an equivalence relation. $\endgroup$ – 111 Feb 7 '18 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.