Understanding The Wagon - From Bandersnatch to Banderwagon

Introduction

This document explains the transformation from bandersnatch to banderwagon. The particular technique for doing this was independently found by Gottfried Herold. In short, he found that one can create a prime order subgroup by quotienting out the group of rational points in the bandersnatch group.

The main purpose is to give one an intuition of why and how banderwagon works. For a concise handling of the topic, check out Gottfried's Implementation notes.

Acknowledgments

Thanks to Gottfried for reading, commenting and correcting both mathematical and grammar mistakes. In particular, Gottfried noted that the use of affine co-ordinates to speak about the points at infinity was imprecise. The section on special points has thus been reduced to only note that these four points exist and not on how to derive them using Bessalov's technique.

Twisted Edwards Curve

We define a Twisted Edwards curve over

$F_p$ as:

$$E_{a,d}:a{x}^2+y^2=1+d{x}^2{y}^2$$

• $x,y,a,d\in F_p^{\ast }$
• $d\ne 1$
• $char(p)\ne 2$

Remark: When

$a=1$ we call this called an Edwards curve. Twisted Edwards curves can therefore be seen as a generalisation of Edwards curves.

Group Law

After choosing the identity point to be

$(0,1)$.

We define the addition of two points

$(x_1,y_1)$,

$(x_2,y_2)$ to be:

$$(x_1,y_1)+(x_2,y_2)=(\frac{x_1{y}_2+y_1{x}_2}{1+d{x}_1{y}_2{y}_1{y}_2},\frac{y_1{y}_2-a{x}_1{x}_2}{1-d{x}_1{x}_2{y}_1{y}_2})=(x_3,y_3)$$

The doubling of a point is :

$$2(x_1,y_1)=(\frac{2x_1{y}_1}{1+d{x}_1^2{y}_1^2},\frac{y_1^2-a{x}_1^2}{1-d{x}_1^2{y}_1^2})=(x_2,y_2)$$

It is possible to replace the denominator in the doubling formula using the curve equation, note that this will speed up the doubling of a point relative to using the point addition formula. Consequently leading to side-channel attacks during scalar multiplication since a doubling can now be differentiated from a addition.

The fact that we can use one formula for both point addition and point doubling is known as unification.

Base Points

Twisted Edwards curves have four base points which can be found when

$x=0$ and

$y=0$.

$x=0$:

We find the following points:

$(0,1)$,

$(0,-1)$

$(0,1)$ is the identity element and

$(0,-1)$ is a rational point of order two. The order can be verified using the group law or by checking that the points and its negation are equal.

• We now refer to
  $(0,-1)$ as
  $D_0$

$y=0$:

We find the following points:

$(\sqrt{\frac{1}{a}},0)$,

$(-\sqrt{\frac{1}{a}},0)$

• We refer to
  $(\sqrt{\frac{1}{a}},0)$ and
  $(-\sqrt{\frac{1}{a}},0)$ as
  $F_0$ and
  $F_1$ respectively

These points are rational and have order 4 if

$a$ is a square.

Remark: All edwards curves have at least 2 rational points of order 4, since

$a=1$ is always a square.

Remark: All twisted edwards curves have an order 2 point

$(0,-1)$

Bandersnatch base points

For the field that bandersnatch is defined over,

$a$ is not a square. This means that

$F_0$ and

$F_1$ are not points in the group.

Special points

These points are referred to as points at infinity or exceptional points. Generally one wants to avoid these points during elliptic curve cryptography. It is analogous to avoiding

$\frac{1}{0}$.

Twisted Edwards Elliptic curves have four points at infinity

$D_1,D_2,F_2,F_3$.

• $D_1,D_2$ have order 2
• $F_2,F_3$ have order 4

Bandersnatch special points

For the field that bandersnatch is defined over,

$d$ is not a square, so

$F_2$ and

$F_3$ are not rational points. However, since

$a$ is also non-square

$D_1$ and

$D_2$ are in the group.

Bandersnatch has two special points in its group. These two points both have order 2.

Bandersnatch Subgroup

The group structure of bandersnatch is

${\mathbb{Z}}_{\mathbb{2}}\times {\mathbb{Z}}_{\mathbb{2}}\times p$, where

$p$ is a prime.

The non-cyclic subgroup which we may refer to as the 2 torsion subgroup is :

$$E[2]=\{(0,1),D_0,D_1,D_2\}$$

Remark: All of these points have order 2 or 1, so it is sufficient to double any point in the bandersnatch group to clear the cofactor. ie one does not need to multiply by the cofactor; 4.
Remark: We may also refer to the 2 torsion subgroup as the small order subgroup.

Bandersnatch group structure

For a point

$P$ in the subgroup, we have the following coset:

$$P+E[2]=\{P+(0,1),P+D_0,P+D_1,P+D_2\}$$

When

$P$ is the neutral element, the coset is

$E[2]$, otherwise when

$P$ is in the prime order subgroup we can explicitly write the coset as:

$$P+E[2]=\{(x,y),(-x,-y),(\frac{1}{\sqrt{ad}}{x}^{-1},\sqrt{\frac{a}{d}}{y}^{-1}),(-\frac{1}{\sqrt{ad}}{x}^{-1},-\sqrt{\frac{a}{d}}{y}^{-1})$$

Notice that each pair of points differ by

$D_0$, we can see this better if we explicitly write:

$$P+E[2]=\{P,P+D_0,P+D_1,P+D_1+D_0\}$$

Halving a point

Halving a point is the opposite of doubling a point.

Given a point

$Q$ in the prime order subgroup of size

$p$. We can halve it by multiplying

$Q$ by

$\frac{p+1}{2}$. This will result in a point

$P$ in the prime order subgroup such that

$2P=Q$.

Observe however that there are 3 more points which when doubled will result in

$Q$ these points are exactly the points in the coset

$P+E[2]$. Moreover, note that since there are no rational points of order 4, the only points which are halvable are the points in the prime order subgroup with 4 solutions; 3 of them have order

$2p$ and one has order

$p$. If

$Q$ is the neutral element then the four solutions are instead

$E[2]$ . See here for an extended explanation.

Necessary condition for halving a point is

$(\frac{1-a{X}^2}{p})=1$

Here it is shown that a necessary condition for halving a bandersnatch point is that

$1-a{X}^2$ must be a square. It is not a sufficient condition and the easiest way to see this, is to notice that it is true for both a prime order point

$(x,y)$ and also

$(-x,-y)$ due to the

$X^2$ term.

It is also shown that:

• $(\frac{1-a{X}^2}{p})=1$ can be used to recognise
  $(\pm x,\pm y)$ when
  $(x,y)$ has prime order
• This checks rejects any point of the form
  $P+D_1$ and
  $P+D_2$
• The number of points that pass this check is
  $2p$

Gottfried (emphasis): In particular, points that pass the check are not at infinity. So we can ignore them, greatly simplifying things.

Quotient group

The

$1-a{X}^2$ checks allows us to reduce the effective group size to

$2p$. It is still not a prime order group and consequently, it is still vulnerable to small subgroup attacks. The usual trick is to check if the point is in the prime order subgroup, however this is expensive and moreover does not need

$1-a{X}^2$.

We want to halve the size of the group from

$2p$ to

$p$ and we will use quotient groups to achieve this. A quotient group can be seen as a method for making two elements equal. The strategy will be to make

$(x,y)$ and

$(-x,-y)$ be seen as a single element; they will be in the same equivalence class.

Example

Lets look at the integers modulo 5 for an intuition of how we will do this.

4 and 9 are different integers in

$\mathbb{Z}$, but in

$\mathbb{Z}\mathbb{/}\mathbb{5}\mathbb{Z}$ they are seen as equivalent. If we were to directly check

$4\stackrel{?}{=}9$ this would fail, but if we check

$4\text{ mod 5}\stackrel{?}{=}\text{9 mod 5}$ this passes. In a way, we have merged

$4$ and

$9$ to be identified as the same element. When we look at them modulo

$5$ they are in the same equivalence class. Following this, the first place to modify will be the equality check between points.

Equality check

To merge

$(x_1,y_1)$ and

$(-x_1,-y_1)$, we no longer check

$x\stackrel{?}{=}-x$ and

$y\stackrel{?}{=}-y$.

We now check:

$\frac{x_1}{y_1}\stackrel{?}{=}\frac{-x_2}{-y_2}$.

In general, for two points

$(x_1,y_1),(x_2,y_2)$, we check they are equal with the equation

$\frac{x_1}{y_1}\stackrel{?}{=}\frac{x_2}{y_2}$. This is equivalent to checking

$x_1\times y_2\stackrel{?}{=}{x}_2\times y_1$

Zero case

Lets analyse the cases when

$x$ or

$y$ are zero.

$x=0$:

When

$x=0$ we have two points which are on the curve and pass the

$1-a{X}^2$ check;

$(0,1)$ and

$(0,-1)$. These two points should be merged and seen as equal since they differ by

$D_0$. They are the identity element of the quotient group.

Note: To check for the identity element, one only needs to check if

$x=0$.

$y=0$:

There is no point on the bandersnatch curve with

$y=0$ due to the fact that

$a$ is non-square.

Note: If the point is not on the curve or does not pass the

$1-a{X}^2$ check, then the equality check is not sound. There should be no API build a banderwagon point without performing these checks. Furthermore, the internal representation should be seen as a blackbox. This is also the suggestion that the Ristretto/Decaf RFC states.

Serialisation

When serialising a point, remember we want

$(x,y)$ and

$(-x,-y)$ to serialise to the same bitstring. This can be done by taking the sign of the

$y$ co-ordinate, multiplying it by the

$x$ co-ordinate and sending the result as a bit string. This works because

$$\text{serialise(x,y) = sign(y)}\times \text{x}$$

$$\text{serialise(-x,-y) = sign(-y)}\times \text{-x = sign(y)}\times \text{x}$$

Deserialisation (Informal)

Upon receiving

$\text{sign(y)}\times \text{x}$, one must check that

$1-a{X}^2$ is a square. The

$\text{sign(y)}$ does not matter as we are squaring

$X$. If this check passes, we then find the corresponding

$y$ using the curve equation.

Note: The curve equation will return

$y$ and

$-y$ for some choice of positiveness. We want to choose positive

$y$. Choosing

$(x,-y)$ will give you an element that is valid, but equivalent to the negation of

$(x,y)$.
Remark: Negating a point in the quotient group can be done by negating either the

$x$ or the

$y$ co-ordinate

Note: If

$p\equiv \text{3 mod 4}$ then the

$\text{sign}$ function can be implemented with a quadratic residue check

Deserialisation (Formal)

This is also described here

• Receive
  $t=\text{sign(y)}\times \text{x}$. This will be a bit string.
• Interpret the bit string
  $\text{t}$ as a field element
  $F_p$ in the interval
  $[0,p-1]$. The interpreted field element is now denoted
  $x_k$.
  $x_k$ will be the
  $x$ co-ordinate of our deserialised point.
• Check whether
  $1-a{x}_k^2$ is a square. If it is not, Abort.
• Using the curve equation, we can find
  $y_k^2=\frac{1-a{x}_k^2}{1-d{x}_k^2}$
• Take the square root of
  $y_k^2$. If it does not exist, Abort.
• Pick the value of
  $y_k$ such that
  $\text{sign}(y_k)=1$

Group law

The group law does not change because what we quotiented by was a subgroup. These are still points on the bandersnatch curve and form a group under point addition.

Map To Field

Since we are only dealing with the points

$(x,y)$ and

$(-x,-y)$ which are considered equal, we can create the following injective maps from the quotient group to the field

$F_p$:

• $\frac{x}{y}$
• $x\times y$

Since

$y\ne 0$ ,

$\frac{x}{y}$ is never undefined. For banderwagon, the choice made was to use

$\frac{x}{y}$, because in projective co-ordinates

$\frac{x}{y}=\frac{X}{Y}$ while

$xy=\frac{XY}{Z^2}$

Remark: This map is not injective if you are mapping from the bandersnatch group to

$F_p$ because for one,

$(x,y)$ and

$(-x,-y)$ are not considered to be equal.

Banderwagon Abstraction

The combination of checking if

$1-a{X}^2$ is a square, and the serialisation strategy over bandersnatch is what is known as banderwagon.

Conclusion

Using banderwagon, one is able to view the group as prime order subgroup with an injective map to the field

$F_p$. Moreover, the points at infinity are not in this prime order group abstraction, so the group law is complete.

Appendix

Theorem 1:

$(\frac{1-d{X}^2}{p})=(\frac{1-a{X}^2}{p})$ when

$X$ is on the curve

Proof.

The curve equation is given as:

$a{x}^2+y^2=1+d{x}^2{y}^2$

$$\to 1-a{x}^2=y^2-d{x}^2{y}^2$$

$$\to 1-a{x}^2=y^2(1-d{x}^2)$$

Hence for a point on the curve,

$1-d{x}^2$ and

$1-a{x}^2$ are either both squares or both non-squares.

Proof done.

This means that we could check if

$1-d{X}^2$ is a square, but this is not done because its more expensive than

$1-a{X}^2$ since

$a$ is smaller than

$d$

Theorem 2:

$(\frac{1-a{x}^2}{p})(\frac{1-y^2}{p})=(\frac{a-d}{p})$

read: the legendre symbol of the lhs is equal to the legendre symbol of the rhs

Proof

$(1-a{x}^2)(1-y^2)$

$(1-y^2)-a{x}^2+a{x}^2{y}^2\text{ (expanding the brackets)}$

$(a{x}^2-d{x}^2{y}^2)-a{x}^2+a{x}^2{y}^2\text{ (using the curve equation)}$

$(a-d)(xy{)}^2\text{ (cancel and group terms)}$

Since

$(xy{)}^2$ is always a quadratic residue, the legendre symbol of

$(a-d)(xy{)}^2$ is determined by

$(a-d)$

Corrolary:

$(\frac{1-a{x}^2}{p})=1\text{ implies }(\frac{1-y^2}{p})=-1$

Given that

$$(\frac{1-a{x}^2}{p})(\frac{1-y^2}{p})=(\frac{a-d}{p})$$

Plugging in our condition:

$$(\frac{1-a{x}^2}{p})=1$$

We arrive at:

$$(\frac{1-y^2}{p})=(\frac{a-d}{p})$$

For bandersnatch,

$a-d$ is a quadratic non-residue, hence it is sufficient to check that:

$$(\frac{1-y^2}{p})=-1$$

It seems that we could check if

$1-y^2$ is a non-residue, instead of checking if

$1-a{X}^2$ is a residue. The problem is that the identity element is an edge case, it would return a legendre symbol of

$0$. We would need to check that case separately, which trades developer complexity for CPU time.

What points are halvable?

Moved to here