Implementing Banderwagon - A Scheme Built on top of Bandersnatch Curve

Not much of big update this week, but it was more of learning and unlearning a lot of things. I figured out what needs to be implemented and how to go about it. So if I try to sum up this week : -

• Learning about how to add a new curve to the constantine library
• Going through the Banderwagon Implementation in Python
• Testing out the few functions needed for Banderwagon using Bandersnatch
• Learning about serialization and deserialization of points on the curve

A Decaf-Style representation of cofactor-4 incomplete twisted Edwards curves

In order to ensure that we only work on the subgroup and also get extremely fast deserialization of untrusted input, we use the following decaf-style (to my knowledge novel, in the context of cofactor-4 incomplete twisted Edwards curves) trick:

We represent $G$ as $G\cong G'/\{N,A\}$, i.e. we work only in $G'$, but we identify $P$ with $P+A$. Explicitly, for $P=(X:Y:T:Z)$, we have $P+A = (-X:-Y:T:Z) = (X:Y:-T:-Z)$. Of course, this means that we no longer have a unique representation of curve points, but we did not have that to start with due to using projective coordinates. Of course, for every element $P\in G'$, exactly one of $P$ and $P+A$ is in $G$ and we could just choose that one; however, this is actually hard to determine and the point is that we do not need to know which one. If a unique representative is really needed, we suggest to choose the one with $Y \in [0, \frac{p-1}{2}]$ and $Z=1$

Now, why is this a good idea? We have the following key properties:

• On $G'$, all points have $Y\neq 0$ and $Z\neq 0$.
• It is much easier to check whether an element is in $G'$ than to check whether it is in $G$.
• Checking whether two curve points $P$ and $Q$ are equal / $P$ is the neutral elements is essentially equally difficult whether we work modulo $A$ or not.
• All curve operations are compatible with this identification.

Let us argue why these properties hold:

The last bullet point is easy: This holds simply because $\{N, A\}$ is a subgroup. The first one is also easily verified by plugging either $Y=0$ or $Z=0$ into the curve equations. In fact, $E_1$ and $E_2$ are the only rational points with either $Y=0$ or $Z=0$.

The other properties are a bit harder: First, we make the following observation: The map $\mathcal{E} \to \mathbb{F}, P \mapsto \frac{X}{Y}$

is 2:1. Indeed the preimage sets (including non-rational points) are exactly of the form $\{P, P+A, -P+I_1, -P+I_2\}$, where $I_1$, $I_2$ are the non-rational points at infinity, as one can easily verify. On $\mathcal{E}$, we hence get a 2:1 map. In particular, when quotienting out $\{N, A\}$ and on $G$, the map is injective. This means that to check equality of points $P_1 = P_2$ modulo our identification, we just need to check whether $\frac{X_1}{Y_1} = \frac{X_2}{Y_2}$, or equivalently $X_1Y_2 = X_2Y_1$. Note that this is just as hard or easy as not doing the identification, where we would need to divide by $Z$ (due to working with projective coordinates) instead of by $Y$. To check whether a point is (equivalent to) the neutral element, we just need to check whether $X=0$.

For the subgroup check, we make the following observation: For any rational point P = (X:Y:T:Z), the following are equivalent:

1. One of $P$, $P+A$ is in $G$
2. $Z^2-aX^2$ is a square in $\mathbb{F}$
3. $Z^2-dX^2$ is a square in $\mathbb{F}$
4. $(aZ^2-dY^2)(a-d)$ is a square in $\mathbb{F}$ and $Z\neq 0$
5. $(aZ^2-dY^2)$ is a non-square in $\mathbb{F}$ and $Z\neq 0$.

Note that we can restrict our attention to $Z\neq 0$. Setting $x= \frac{X}{Z}$, $y = \frac{Y}{Z}$, we have $x^2 = \frac{1-y^2}{a-dy^2}$ resp. $y^2 = \frac{1-ax^2}{1-dx^2}$. Together with checking that $a-d$ is a non-square, this is enough to show that 2—5 are equivalent. The tricky part is equivalence with 1. The easiest way is probably observing that $P$ is in $G$ iff $P = Q + Q$ has a solution for rational $Q$. Writing this out shows that 2—5 are neccessary. To show that it is sufficient, observe that conditions 2—5 hold for exactly one of $P, P+E_1$. This is also true for condition 1 due to the group structure of $\mathcal{E}$.

This observation allows us to test membership in $G'$ by a computation of a Jacobi symbol, which is considerably faster than computing a square root in $\mathbb{F}$ or any exponentiation involving $P$.

Implementation

This is the subgroup check that I need to implement. This would be further used while loading a point from bytes32 to a point on the curve.

## TODO: change this to return true/false
    def subgroup_check(x: Fp):
        # Compute 1 - aX^2 and check its legendre symbol
        res = Fp.zero()
        res.mul(x, x)
        res.mul(res, A_COEFF)
        res.neg(res)
        res.add(res, Fp.one())

        return res.legendre()

Next would be the equality check

def __eq__(self, other):
        if isinstance(other, Banderwagon):
            # The equals method is different for the quotient group
            #
            # Check for the (0,0) point, which is _possible_
            # given that you do not need to use the constructor to construct points
            x1 = self.point.x
            y1 = self.point.y
            x2 = other.point.x
            y2 = other.point.y

            if x1.is_zero() and y1.is_zero():
                return False
            if x2.is_zero() and y2.is_zero():
                return False

            lhs = x1 * y2
            rhs = x2 * y1

            return lhs == rhs

There might be few other things that might be needed to implement, but till now I have figured out these two. I will be working on this for the next week in Nim.