ed448goldilocks/_aux/ristretto/ristretto.tex

\documentclass[11pt]{article}

\usepackage{amsmath,amsthm,amsfonts,amssymb,xspace,graphicx,url,stmaryrd,parskip}

\newtheorem{lemma}{Lemma}

\newcommand\todo[1]{\textbf{[[TODO: #1]]}\xspace}
\def\F{\ensuremath{\mathbb{F}}}
\def\G{\ensuremath{\mathbb{G}}}
\def\Z{\ensuremath{\mathbb{Z}}}
\def\O{\ensuremath{O}}

\begin{document}
\title{The Ristretto and Cortado elliptic curve groups}
\author{Mike Hamburg\thanks{Rambus Security Division}}
\maketitle

\begin{abstract}
\end{abstract}

\section{Introduction}
\section{Definitions and notation}

Let the symbol $\bot$ denote failure.

\subsection{Field elements}
Let \F\ be a finite field of prime order $p$.  For an element $x\in\F$, let $\text{res}(x)$ be the integer representative of $x\in[0,p-1]$.  We call an element $x\in\F$ \textit{negative} if $\text{res}(x)$ is odd.  Call an element in \F\ \textit{square} if it is a quadratic residue, i.e.\ if there exists $\sqrt{x}\in\F$ such that $\sqrt{x}^2=x$.  There will in general be two such square roots; let the notation $\sqrt{x}$ mean the unique non-negative square root of $x$.  If $p\equiv1\pmod 4$, then \F\ contains an element $i := \sqrt{-1}$.

Let $\ell := \lceil \log_{2^8} p\rceil$.  Each $x\in\F$ has a unique \textit{little-endian byte representation}, namely the sequence
$$
\text{\F\_to\_bytes}(x) := \llbracket b_i\rrbracket_{i=0}^{\l-1} \ \text{where}\ b_i\in[0,255]\text{\ and\ }\sum_{i=0}^{\l-1} 2^{8i} \cdot b_i = \text{res}(x)
$$
\todo{bytes to \F}

\subsection{Groups}
For an abelian group \G\ with identity \O, let $n\G$ denote the subgroup of $\G$ which are of the form $n\cdot g$ for some $g\in\G$.  Let $\G_n$ denote the $n$-torsion group of \G, namely the subgroup $\{g\in\G : n\cdot g = O\}$.

\subsection{Edwards curves}
We will work with twisted Edwards elliptic curves of the form 
%
$$E_{a,d} : y^2 + a\cdot x^2 = 1 + d\cdot x^2\cdot y^2$$
%
where $x,y\in\F$. Twisted Edwards curves curves have a group law
$$(x_1,y_1) + (x_2,y_2) := 
\left(
\frac{x_1 y_2 + x_2 y_1}{1+d x_1 x_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}
\right)
$$
with identity point $\O := (0,1)$ and group inverse operation $$-(x,y) = (-x,y)$$
The group law is called \textit{complete} if is produces the correct answer (rather than e.g.\ $0/0$) for all points on the curve.  The above formulas are complete when $d$ and $ad$ are nonsquare in \F, which implies that $a$ is square.  When these conditions hold, we also say that the curve itself is complete.

Let the number of points on the curve be $$\#E_{a,d} = h\cdot q$$ where $q$ is prime and $h\in\{4,8\}$.  We call $h$ the \textit{cofactor}.

For $P = (x,y)\in E$, we can define the \textit{projective homogeneous form} of $P$ as $(X,Y,Z)$ with $Z\neq 0$ and $$(x,y) = (X/Z,Y/Z)$$ and the \textit{extended homogeneous form} as $(X,Y,Z,T)$ where additionally $XY=ZT$.  Extended homogeneous form is popular because it supports simple and efficient complete addition formulas~\cite{hisil}.

\subsection{Montgomery curves}

When $a-d$ is square in \F, the twisted Edwards curve $E_{a,d}$ is isomorphic to the Montgomery curve
$$v^2 = u\cdot\left(u^2 + 2\cdot\frac{a+d}{a-d}\cdot u + 1\right)$$
by the map
$$(u,v) = \left(\frac{1+y}{1-y},\ \ \frac{1+y}{1-y}\cdot\frac1x\cdot\frac{2}{\sqrt{a-d}}\right)$$
with inverse
$$(x,y) = \left(\frac{u}{v}\cdot\frac{\sqrt{a-d}}{2},\ \ \frac{u-1}{u+1}\right)$$

If $M = (u,v)$ is a point on the Montgomery curve, then the $u$-coordinate of $2M$ is $(u^2-1)^2 / (4v^2)$ is necessarily square.  It follows that if $(x,y)$ is a point on $E_{a,d}$, and $a-d$ is square, then $(1+y)/(1-y)$ is also square.

Likewhise, when $d-a$ is square in \F, $E_{a,d}$ is isomorphic to the Montgomery curve
$$v^2 = u\cdot\left(u^2 - 2\cdot\frac{a+d}{a-d}\cdot u + 1\right)$$
by the map
$$(u,v) = \left(\frac{y+1}{y-1},\ \ \frac{y+1}{y-1}\cdot\frac1x\cdot\frac{2}{\sqrt{d-a}}\right)$$
with inverse
$$(x,y) = \left(\frac{u}{v}\cdot\frac{\sqrt{d-a}}{2},\ \ \frac{1+u}{1-u}\right)$$

\section{Lemmas}
First, we characterize the 2-torsion and 4-torsion groups.\\
\begin{lemma}\label{lemma:tors}
Let $E_{a,d}$ be a complete Edwards curve.  Its 2-torsion subgroup is generated by $(0,-1)$.  The 4-torsion subgroup is generated by $(1/\sqrt{a},0)$.

Adding the 2-torsion generator to $(x,y)$ produces $(-x,-y)$.  Adding the 4-torsion generator $(1/\sqrt{a},0)$ produces $(y/\sqrt{a},-x\cdot\sqrt{a})$
\end{lemma}
\begin{proof}
Inspection.
\end{proof}

\begin{lemma}\label{lemma:line}
Let $E_{a,d}$ be a complete twisted Edwards curve over \F, and $P_1 = (x_1,y_1)$ be any point on it.  Then there are exactly two points $P_2 = (x_2,y_2)$ satisfying $x_1 y_2 = x_2 y_1$, namely $P_1$ itself and $(-x_1,-y_1)$.  That is, there are either 0 or 2 points on any line through the origin.
\end{lemma}
\begin{proof}
Plugging into the group operation gives
$$x_1 y_2 = x_2 y_1 \Longleftrightarrow P_1-P_2 = (0,y_3)$$
for some $y_3$.  Plugging $x=0$ into the curve equation gives $y=\pm1$, the 2-torsion points.  Adding back, we have $P_2 = P_1 + (0,\pm1) = (\pm x_1, \pm y_1)$ as claimed.
\end{proof}

\begin{lemma}\label{lemma:dma}
If $E_{a,d}$ is a complete Edwards curve, then $a^2-ad$ is square in \F\ (and thus $a-d$ is square in \F) if and only if the cofactor of $E_{a,d}$ is divisible by 8.
\end{lemma}
\begin{proof}
Doubling an 8-torsion generator $(x,y)$ should produce a 4-torsion generator, i.e.\ a point with $y=0$.  From the doubling formula, this happens precisely when $y^2=ax^2$, or $2ax^2=1+adx^4$.  This has roots in \F\ if and only if its discriminant $4a^2-4ad$ is square, so that $a^2-ad$ is square.
\end{proof}

\begin{lemma}\label{lemma:sqrt}
If $(x_2,y_2) = 2\cdot(x_1,y_1)$ is an even point in $E_{a,d}$, then $(1-ax_2^2)$ is a quadratic residue in \F.  \todo{$(y_2^2-1)$}.
\end{lemma}
\begin{proof}
The doubling formula has $$x_2 = \frac{2x_1 y_1}{y_1^2+ax_1^2}$$
so that $$1-ax_2^2 = \left(\frac{y_1^2-ax_1^2}{y_1^2+ax_1^2}\right)^2$$
is a quadratic residue.  Now for any point $(x,y)\in E_{a,d}$, we have
$$(y^2-1)\cdot(1-ax^2)
= y^2+ax^2-1-ax^2y^2
= (d-a)x^2y^2
$$
which is a quadratic residue by Lemma~\ref{lemma:dma}.
\end{proof}

\section{The Espresso groups}
Let $E$ be a complete twisted Edwards curve with $a\in\{\pm1\}$ and cofactor $4$ or $8$. We describe the \textit{Espresso} group $\G(E)$ as
$$\text{Espresso}(E) := 2E / E_{h/2}$$
This group has prime order $q$.
\subsection{Group law}
The group law on $\text{Espresso}(E)$ is the same as that on $E$.
\subsection{Equality}
Two elements $P_1 := (x_1,y_1)$ and $P_2 := (x_2,y_2)$ in $\text{Espresso}(E)$ are equal if they differ by an element of $E_{h/2}$.

If $h=4$, the points are equal if $P_1-P_2\in E_2$.  By Lemma~\ref{lemma:line}, this is equivalent to $$x_1 y_2 = x_2 y_1$$

If $h=8$, the points are equal if $P_1-P_2\in E_4$.  By Lemmas~\ref{lemma:tors} and~\ref{lemma:line}, this is equivalent to $$x_1 y_2 = x_2 y_1\text{\ \ or\ \ }x_1 x_2 = -a y_1 y_2$$

These equations are homogeneous, so they may be evaluated in projective homogeneous form with $X_i$ and $Y_i$ in place of $x_i$ and $y_i$

\subsection{Encoding}
We now describe how to encode a point $P = (x,y)$ to bytes.  The requirements of encoding are that
\begin{itemize}
\item Any point $P\in2E$ can be encoded.
\item Two points $P,Q$ have the same encoding if and only if $P-Q\in E_{h/2}$.
\end{itemize}

When $h=4$, we encode a point as $\sqrt{a(y-1)/(y+1)}$

\end{document}