19
$\begingroup$

In a recent question on using the same curve for signing and ECDH it was noted for the Ed25519 curve and Curve25519:

Nitpick: the curves are birationally equivalent, not isomorphic.

Now this term shows up quite often in cryptography, especially when one is concerned with the differences and transformations between various curve representations. So my question:

For a "cryptographer" who has never heard of "varieties" or "functional fields" what does "birational equivalence" state for the relation between two groups / rings / fields?

I have searched around a bit but usually most explanations use this advanced algebraic terminology and I'd just like to have a "simple" explanation / intuition for the day-to-day algebra in cryptography.

$\endgroup$
23
$\begingroup$

I feel that as it was my comment, I am obliged to answer this :-).

First of all, birational equivalence is really a geometric notion. As far as I know, there is no analogue for groups, rings or fields and therefore the cryptographic relevance is limited. It becomes relevant when speaking of geometric objects: for example, elliptic curves.

Given these geometric objects, we want to define what it means to be "the same". The usual terminology is that given two curves $E_1$ and $E_2$, they are "the same" when they are isomorphic. There is another way to equate objects, and that is by saying that they are "almost the same". This is what a birational equivalence does: two curves $E_1$ and $E_2$ are birationally equivalent when there is a map $\phi:E_1\rightarrow E_2$ between them which is defined at every point of $E_1$ except a small set of exceptions and there is an inverse map $\phi^{-1}:E_2\rightarrow E_1$ which is defined at every point of $E_2$ except a small set of exceptions. This definition is very close to that of an isomorphism, except for the fact that we allow some exceptions.

To make this more concrete, you could think of an isomorphism as a tuple of polynomials:

$$\psi:E_1\rightarrow E_2,\quad (x,y)\mapsto (f(x,y),g(x,y)),$$ where $f,g$ are polynomials in $x,y$. The inverse is also defined in terms of polynomials.

A birational map can be thought of as a tuple of fractions of polynomials, say

$$\phi:E_1\rightarrow E_2,\quad (x,y)\mapsto \left(\frac{f_1(x,y)}{f_2(x,y)},\frac{g_1(x,y)}{g_2(x,y)}\right).$$

This is defined at all points $(x,y)$ except for the ones where $f_2(x,y)=0$ or $g_2(x,y)=0$. The inverse is also a fraction of polynomials, and can therefore be undefined at certain points.

Now let's make this even more concrete, and follow the Ed25519 paper. The Curve25519 curve is defined by $$E_1:v^2=u^3+486662u^2+u.$$ It is birationally equivalent to the Edwards curve given by $$E_2:x^2+y^2=1+\frac{121665}{121666}x^2y^2.$$ The birational equivalence is given by the map $\phi:E_1\rightarrow E_2$ defined by $$\phi(u,v)=\left(\frac{\sqrt{486664}u}{v},\frac{u-1}{u+1}\right).$$ Notice that it is undefined for $v=0$ or $u=-1$, and therefore is not an isomorphism. The inverse map is defined by $$\phi^{-1}(x,y)=\left(\frac{1+y}{1-y},\frac{\sqrt{486664}u}{x}\right).$$ Again, it is undefined for $y=1$ or $x=0$.

Finally, consider the twisted Edwards curve $$E_3:-x^2+y^2=1-\frac{121665}{121666}x^2y^2.$$ There is a map $\psi:E_2\rightarrow E_3$ defined by $\psi(x,y)=\left(ix,y\right)$, assuming that $i$ is a square root of $-1$. This is clearly defined everywhere, and is an isomorphism.

$\endgroup$
  • 2
    $\begingroup$ In fact, they would be isomorphic in a category whose arrows are rational maps! $\endgroup$ – Hurkyl Jan 16 '17 at 18:58
  • $\begingroup$ Would an elementary example be that (x^3 + x^2 + x - 3)/(x - 1) is equivalent to x^2 + 2x + 3 except that one has a hole in it at x=1 and the other doesn't? $\endgroup$ – hobbs Jan 17 '17 at 8:47
  • $\begingroup$ @hobbs That sounds about right, although you may want to make that precise. They are "equivalent" in the sense that they correspond to the same element in the function field, whereas they are different when viewed as fractions of polynomials (since one is clearly undefined at $x=1$, while the other is not). $\endgroup$ – CurveEnthusiast Jan 17 '17 at 10:22
  • 1
    $\begingroup$ One additional notion of sameness is important in the setting of cryptography: Does the birational map preserve the addition law in the group of $k$-rational points, at least for those points on which it is defined? (Answer: yes, but this is not obvious to an outsider to algebraic geometry.) $\endgroup$ – Squeamish Ossifrage Aug 27 '17 at 16:17
  • $\begingroup$ Using the dictionary between algebra and geometry, provided by algebraic geometry, you could talk of an analogue of a birational equivalence between rings $R_1, R_2$, as long as they are integral domains. It would simply be that there is an isomorphism $\mathrm{Frac}(R_1) \cong \mathrm{Frac}(R_2)$ between their fraction fields. Or perhaps a better definition, more faithful to geometry, could be that there is an isomorphism $\mathrm{Frac}(R_1) \supset R_1[f_1^{-1},\dots,f_m^{-1}] \cong R_2[g_1^{-1},\dots,g_n^{-1}] \subset \mathrm{Frac}(R_2)$ between finitely generated localizations. $\endgroup$ – PrimeRibeyeDeal Aug 28 '18 at 18:24
1
$\begingroup$

The notion of isomorphism between two group varieties (as elliptic curves, which are algebraic varieties of dimension 1, or Jacobian of curves), implies a group isomorphism. So the geometry, provides some information about the algebra. The notion birational in case of curves (where the definition was given by the previous poster) has to do with the genus of the curves. The following theorem holds : two curves are birational if-f have the same genus. Of course an isomorphism is a birational map.

$\endgroup$

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.