# Encoding with Isogenies

The Decaf strategy is to define an encoding of $$\mathcal J / \mathcal J[2]$$, the Jacobi quartic modulo its $$2$$-torsion, and then to transport the encoding to an Edwards or Montgomery curve used to implement the group operations. Ristretto uses the same strategy, but makes different choices for encoding $$\mathcal J / \mathcal J[2]$$ and explicitly supports the cofactor-$$8$$ case.

## Encoding $$\mathcal J / \mathcal J[2]$$

As noted in the Curve Models section, the $$\mathcal J[2]$$-coset of a point $$P = (s,t)$$ on $$\mathcal J_{a^2, A}$$ is $P + \mathcal J[2] = \left\{ (s,t), (-s,-t), (1/as, -t/as^2), (-1/as, t/as^2) \right\}.$

To encode points on $$\mathcal J$$ modulo $$\mathcal J[2]$$, we need to choose a canonical representative of the above coset. The encoding is then the (canonical byte encoding of the) $$s$$-value of the canonical representative.

To do this, it's sufficient to make two independent sign choices; Decaf chooses the $$(s,t)$$ with $$s$$ non-negative and finite, and $$t/s$$ non-negative or infinite. Ristretto makes different sign choices, discussed later.

## Transporting an encoding along an isogeny

The Decaf paper recalls that, for a group $$G$$ with normal subgroup $$G' \leq G$$, a group homomorphism $$\phi : G \rightarrow H$$ induces a homomorphism $$\bar{\phi} : \frac G {G'} \longrightarrow \frac {\phi(G)}{\phi(G')} \leq \frac {H} {\phi(G')},$$ and that the induced homomorphism $$\bar{\phi}$$ is injective if $$\ker \phi \leq G'$$.

Both $$\phi : \mathcal J \rightarrow \mathcal E_1$$ and $$\theta : \mathcal J \rightarrow \mathcal E_2$$ have kernels contained in $$\mathcal J[2]$$, and give isomorphisms $$\frac {\mathcal J} {\mathcal J[2]} \cong \frac {\phi(\mathcal J)} {\phi(\mathcal J[2])} \cong \frac {[2](\mathcal E_1)} {\mathcal E_1[2]}, \qquad \frac {\mathcal J} {\mathcal J[2]} \cong \frac {\theta(\mathcal J)} {\theta(\mathcal J[2])} \cong \frac {[2](\mathcal E_2)} {\mathcal E_2[2]}.$$

We can use these isomorphisms to transfer an encoding of $$\mathcal J / \mathcal J[2]$$ to $$[2](\mathcal E)/\mathcal E[2]$$ for either choice of $$\mathcal E = \mathcal E_1, \mathcal E_2$$.

In the cofactor $$4$$ case, where $$\# \mathcal E(\mathbb F_p) = 4\cdot \ell$$, $$[2](\mathcal E)/\mathcal E[2]$$ has prime order $$(4\ell/2)/2 = \ell$$ and we're done.

In the cofactor $$8$$ case with cyclic $$8$$-torsion, we have $$[2](\mathcal E[8]) = \mathcal E[4]$$, so that $$\mathcal E[4] \subseteq [2](\mathcal E)$$. The group $$[2](\mathcal E)/\mathcal E[4]$$ has prime order $$(8\ell/2)/4 = \ell$$, and to encode it we use the torquing procedure described below to canonically lift $$\mathcal E / \mathcal E[4]$$ to $$\mathcal E / \mathcal E[2]$$, and then apply the encoding above.

## Torquing points to lift $$\mathcal E / \mathcal E[4]$$ to $$\mathcal E / \mathcal E[2]$$

To bridge the gap between the cofactor $$4$$ and cofactor $$8$$ cases, we need a way to canonically select a representative modulo $$\mathcal E[2]$$, given a representative modulo $$\mathcal E[4]$$.

Using the description of $$\mathcal E[4]$$ in the Curve Models section, we can write the $$\mathcal E[4]$$-coset of a point $$P = (x,y)$$ as $$P + \mathcal E_{a,d}[4] = \{ (x,y),\; (y/\sqrt a, -x\sqrt a),\; (-x, -y),\; (-y/\sqrt a, x\sqrt a)\}.$$ Notice that if $$xy \neq 0$$, then exactly two of these points have $$xy$$ non-negative, and they differ by the $$2$$-torsion point $$(0,-1)$$.

This means that we can select a representative modulo $$\mathcal E[2]$$ by requiring $$xy$$ nonnegative and $$y \neq 0$$, and we can ensure that this condition holds by conditionally adding a $$4$$-torsion point $$Q_4$$ if $$xy$$ is negative or $$y = 0$$.

The points of exact order $$4$$ are $$(\pm 1/\sqrt{a}, 0 )$$; convenient choices for $$Q_4$$ are $$(1,0)$$ when $$a = 1$$ and $$(i, 0)$$ when $$a = -1$$, although the choice of which $$4$$-torsion point to use doesn't matter.

This procedure gives a canonical lift from $$\mathcal E / \mathcal E[4]$$ to $$\mathcal E / \mathcal E[2]$$. Since it involves a conditional rotation, we refer to it as torquing the point.

## Ristretto and Decaf

Decaf is oriented around use of the curve $$\mathcal E_1 = \mathcal E_{a_1,d_1}$$, while Ristretto is oriented around use of the curve $$\mathcal E_2 = \mathcal E_{a_2, d_2}$$. The correspondence between the Ristretto parameters $$a_2 , d_2$$ and the Decaf parameters $$a_1, d_1$$ is given by \begin{aligned} a_2 &= -a_1 & a_1 &= -a_2 \\ d_2 &= \frac {a_1 d_1} {a_1 - d_1} & d_1 &= \frac {a_2 d_2 }{a_2 - d_2} \\ \end{aligned} When using the Edwards form of Curve25519 to implement the group, as in ristretto255, this approach has the advantage that when $$a_2, d_2$$ are the Ed25519 parameters $$-1, -121665/121666$$, $$a_1, d_1$$ are $$1, -121666$$. This allows a compatible implementation to implement group operations on the curve $$\mathcal E_1$$ or its $$-1$$ twist $$\mathcal E_{-1, 121666}$$, which has smaller constants and therefore slightly better performance.