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:

One of $P$, $P+A$ is in $G$
$Z^2-aX^2$ is a square in $\mathbb{F}$
$Z^2-dX^2$ is a square in $\mathbb{F}$
$(aZ^2-dY^2)(a-d)$ is a square in $\mathbb{F}$ and $Z\neq 0$
$(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.