\documentclass{beamer}

% for themes, etc.
\mode<presentation>
{ \usetheme{boadilla} }
\useoutertheme[subsection=false]{}
\setbeamertemplate{navigation symbols}{}
\colorlet{lightblue}{blue!5!white}
\colorlet{mygreen}{green!50!black}
\setbeamertemplate{background canvas}[vertical shading][top=lightblue,bottom=white]
\setbeamersize{text margin left=1.5 cm, text margin right=1.5 cm} 
\setbeamercovered{transparent}




\usepackage{times,color}  % fonts are up to you
\usepackage{graphicx,multirow}
\usepackage{amsthm,amsmath}
\usepackage{appendixnumberbeamer}
\def\Tiny{\fontsize{5pt}{5pt}\selectfont}
\def\nodiv{\mbox{$ {\not |\, } $}} 
\newcommand{\Fp}{\mathbb{F}_p}

% these will be used later in the title page
\title[Isogenies and Quantum Computing]{Isogenies in Elliptic Curve Cryptography}
\author[D. Moody]{Dustin Moody}
\institute[NIST]{
  Computer Security Division\\
  National Institute of Standards and Technology\\[1ex]
  \texttt{dustin.moody@nist.gov}
}
\date[Jan. 25, 2013]{January 25, 2013}




\begin{document}

% this prints title, author etc. info from above
%\begin{frame}
%\titlepage
%\end{frame}


\begin{frame}
\frametitle{Outline}
\begin{itemize}
\item Background on Isogenies 
\vspace{10 pt}
\item Rostovstev and Stolbunov's cryposystem
\vspace{10 pt}
\item "Constructing elliptic curve isogenies in quantum subexponential time," (Childs, Jao, Soukharev) 2011
\vspace{10 pt}
\item "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies," (Jao, de Feo) 2011
\end{itemize}
\end{frame}

\begin{frame}{Elliptic Curve} 
Let $K$ be a field.

An elliptic curve $E$ is a nonsingular curve of genus 1 with at least one $K$-rational point.
\begin{itemize}
\item Weierstrass form $$E: y^2+a_1 xy + a_3 xy=x^3+a_2x^2+a_4x+a_6.$$
\item Short Weierstrass form {\small (char($K)\neq 2,3)$}:  $$E:y^2=x^3+ax+b.$$
\end{itemize}
\begin{figure}
\includegraphics[width = 2 in]{ellipticcurve.jpg}
\end{figure}
\end{frame}

\section{Isogenies}
\begin{frame}{Isogenies}
\begin{itemize}
\item An isogeny $\phi$ is a non-constant homomorphism between elliptic curves given by rational maps.
\item Examples:
\begin{itemize}
\item Let $\phi:E \to E$ be defined by $\phi(P)=P+P+...+P=[n]P$, for some integer $n$.
\item Let $E$ be defined over $\mathbb{F}_p$.  Let $\pi:E \to E$ where $\pi(x,y)=(x^p,y^p).$  The isogeny $\pi$ is known as the \emph{Frobenius}.
\end{itemize}
\item Given a finite subgroup $F$ of $E(K)$, there is an isogeny $\phi:E \to E/F$ such that ker$(\phi)=F$.  
\item If $|F|=\ell$, then the degree of $\phi$ is $\ell$, and $\phi$ is an $\ell$-isogeny.
\end{itemize}
\end{frame}

\begin{frame}{V\'elu's formula}
\begin{itemize}
\item Let $E$ be an elliptic curve with finite subgroup $F$.  Then there is an isogeny $\phi$ from $E$ with kernel $F$.
\item For $P=(x_P,y_P) \notin F$, let 
$$\phi(P)=\Bigg(x_P+\sum_{\substack{Q \in F, \\Q \neq \infty}} (x_{P+Q}-x_Q),y_P+\sum_{\substack{Q \in F, \\Q \neq \infty}} (y_{P+Q}-y_Q)   \Bigg).$$
\item If $|F|=\ell$, then $\phi$ is known as an $\ell$-isogeny.
\end{itemize}
\end{frame}

\begin{frame}{V\'elu's formula - alternate version}
\begin{itemize}
\item Let $\phi$ be an $\ell$-isogeny, with $\ell$ odd.
\item Let $$\aligned D(x)&=\prod_{\infty \neq Q \in F, } (x-x_Q)  \\&=x^{\ell-1}-\sigma x^{\ell-2}+\dots \\&=g(x)^2. \endaligned$$
\item Then $\phi(x,y)=(R(x),yR'(x))$, with
$$R(x)=\ell x-\sigma-(3x^2+a)\frac{D'(x)}{D(x)}-2(x^3+ax+b)\Big(\frac{D'(x)}{D(x)} \Big)'.$$
\item So $\phi$ is completely determined by $D(x)=g(x)^2$.  
\item $g(x)$ is known as the \emph{kernel polynomial}
\end{itemize}
\end{frame}

\begin{frame}{Applications}
\begin{itemize}
\item SEA algorithm - count number of points on an elliptic curve over finite field
\item Distortion maps - needed for pairing-based crypto
\item Efficient point multiplication - key operation in ECC
\item Avoid ZVP attack
\item Random number generator
\item Isogeny volcanoes 
\item Security - isogenies transfer Discrete Log Problem between curves
\item Public key cryptosystems
\end{itemize}
\end{frame}

\begin{frame}{Ordinary and Supersingular}
\begin{itemize}
\item Let $K=\mathbb{F}_p$
\item Then $\#(E(\mathbb{F}_p))=p+1-t$, for some $t \leq 2\sqrt{p}$.
\item If $p|t$, then $E$ is \emph{supersingular}, otherwise $E$ is \emph{ordinary}
\item Most elliptic curves are ordinary
\item Supersingular curves have more special properties
\end{itemize}
\end{frame}

\begin{frame}{Hard Problem}
\begin{itemize}
\item Tate's Theorem:  $E_1$ is $\Fp$-isogenous to $E_2$ if and only if $\#(E_1(\Fp))=\#(E_2(\Fp))$.
\vspace{10 pt}
\item Hard Problem:  Given $\#(E_1(\Fp))=\#(E_2(\Fp))$, find an isogeny from $E_1$ to $E_2$.
\end{itemize}
\begin{figure}
\includegraphics[width = 3 in]{hardproblem.jpg}
\end{figure}
\end{frame}

\begin{frame}{Isogeny Graphs}
\begin{itemize}
\item Fact: $E_1$ and $E_2$ are isomorphic if and only if $j(E_1)=j(E_2)$, 
$$j(E)=\frac{4a^3}{4a^3+27b^2}.$$ 
\item $\ell$-Isogeny Graph
\begin{itemize}
\item Vertices: $j$-invariants of elliptic curves
\item Edges: Connect $E_1$ and $E_2$ if they are $\ell$-isogenous
\end{itemize}
\end{itemize}
\begin{figure}
\includegraphics[width = 2 in]{volcano.jpg}
\end{figure}
\end{frame}

\begin{frame}{Isogeny Stars}
\begin{itemize}
\item Let $E$ be an ordinary elliptic curve with $\#(E(\Fp))=p+1-t$.
\item Let $D=t^2-4p$.  Let $\ell$ be a prime such that $D$ is a square mod $\ell$.  
\item Choose parameters so that number of vertices is prime.
\item Then the $\ell$-isogeny graph containing $E$ is a cycle.  
\item Example: Over $\mathbb{F}_{83}$, there are 7 curves with $t=9$.  
\end{itemize}
\begin{figure}
\includegraphics[width = 3in]{star.jpg}
\end{figure}
\end{frame}

\begin{frame}{Routes}
\begin{figure}
\includegraphics[width = 3in]{stardirection.jpg}
\end{figure}
\begin{itemize}
\item There is a way to fix a direction on an isogeny star.
\item Let $R^{\ell}_{i}$ denote walking $i$ steps on $\ell$-star
\item Key observation: $R^{\ell}_i R^{\ell '}_j = R^{\ell '}_j R^{\ell}_i$
\item Example:
\begin{itemize}
\item Start at 34, with $i=4$, $j=3$.
\end{itemize}
\item A step on a route is computing an isogeny.
\end{itemize}
\end{frame}

\begin{frame}{Rostovtsev and Stolbunov's cryptosystem}
\begin{itemize}
\item Encryption:
\begin{itemize}
\item Agree on all parameters ($\Fp, \ell, \ell', t,$ etc...)
\item Private key: route $R_{priv}$
\item Public key: curve $E$, and curve $E_{pub}=R_{priv}(E)$
\item To send $m$, Bob picks random route $R_{enc}$ and computes $E_{enc}=R_{enc}(E_{pub})$.
\item Bob sends $(s,E')$ to Alice, where $s=m\cdot j(E_{enc})$ and $E'=R_{enc}(E)$.
\item Alice decrypts by computing $j=j(R_{priv}(E')$, and $m=s/j$.
\end{itemize}
\item Diffie-Hellman-ish key exchange:
\begin{itemize}
\item $E$ is fixed.  Alice sends $E_1=R_1(E)$ to Bob.  Bob sends $E_2=R_2(E)$ to Alice.
\item They can both compute $E_{key}=R_1(E_2)=R_2(E_1)$.  
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Security}
\begin{itemize}
\item To break the system, given $E_1$ and $E_2$, need to find a route $R(E_1)=E_2$.  

-- That is, compute an isogeny between $E_1$ and $E_2$.  
\item Timings: For 128 bit security, $\approx$229 seconds to encrypt/decrypt. (normal CPU)
\item The graph isn't computable 
\item Best attack is a meet-in-the-middle attack: Galbraith's algorithm, $O(\sqrt[4]{p})$.  
\item Mainly of theoretical interest.  
\item Possible post-quantum cryptosystem.
\end{itemize}
\end{frame}

\begin{frame}
\begin{figure}
\includegraphics[width = 3.5 in]{table.jpg}
\end{figure}
\end{frame}

\begin{frame}{Childs, Jao, Soukharev}
\begin{itemize}
\item Quantum, subexponential algorithm to compute (horizontal) isogenies.
\item Algorithm is $L_p(\frac{1}{2},\frac{\sqrt{3}}{2}+\sqrt{2})$, with polynomial space
\item Assumes Generalized Riemann Hypothesis
\item Key Idea: reduce to Hidden Shift Problem
\end{itemize}
\end{frame}

\begin{frame}{Hidden Shift Problem}
\begin{itemize}
\item Let $A$ be a finite abelian group, and $S$ a finite set.
\item Let $f_0,f_1:A \to S$ be injective functions.
\item There is a \emph{hidden shift} if 
$$f_1(x)=f_0(xs)$$
for some $s \in A$.  
\begin{block}{Hidden Shift Problem (HSP)}
Given $A,S$ and $f_0,f_1$ with a hidden shift, find $s$.
\end{block}
\end{itemize}
\end{frame}

\begin{frame}{Representing Isogenies}
\begin{itemize}
\item Let $\phi:E \to E'$ be an isogeny over $\Fp$.
\item Recall $\#(E(\Fp))=\#(E'(\Fp))=p+1-t$.  Let $D=t^2-4p <0$.
\item Fact: When $E$ is ordinary, End($E$) is an order $\mathcal{O}$ in $K=\mathbb{Q}(\sqrt{D})$.
\item The isogeny $\phi$ is determined by $E$ and ker$(\phi)$ (up to isomorphism).  
\item ker$(\phi)$ can be represented as an ideal $\mathfrak{b}$ in $\mathcal{O}$.
\end{itemize}
\vspace{20 pt}
$$\phi:E \to E_\mathfrak{b} \longleftrightarrow \mbox{ker}(\phi) \longleftrightarrow \mathfrak{b} \subseteq \mathcal{O}_K$$
\end{frame}

\begin{frame}{Isogenies and Class Groups}
$$\phi:E \to E_\mathfrak{b} \longleftrightarrow \mbox{ker}(\phi) \longleftrightarrow \mathfrak{b} \subseteq \mathcal{O}_K$$
\begin{itemize}
\item Principal ideals $(\mathfrak{a})$ correspond to isomorphisms.
\item Thus, the class group acts on ordinary, isogenous curves with the same endomorphism ring.
\item This defines an operator $*$
$$[\mathfrak{b}] * j(E) \to j(E_\mathfrak{b}),$$
where $[\mathfrak{b}]$ is the ideal class of $\mathfrak{b}$.  
\end{itemize}
\end{frame}

\begin{frame}{Reducing Isogenies to HSP}
\begin{itemize}
\item Let $\phi:E_0 \to E_1$ be an isogeny.
\item Let $\mathfrak{b}$ be the ideal corresponding to $\phi$.
\item Let $f_i([x]) \to [x] * j(E_i)$, for $i=0,1$.
\item Then
$$\begin{aligned}
f_1([x])&=[x] * j(E_1)\\
&=[x] * \left([\mathfrak{b}] * j(E_0)\right)\\
&=([x][\mathfrak{b}]) * j(E_0)\\
&=f_0([x][\mathfrak{b}]).
\end{aligned}$$
\item Thus the isogeny problem reduces to the Hidden Shift Problem.
\end{itemize}
\end{frame}

\begin{frame}{Solving the HSP}
\begin{itemize}
\item Evaluating $f_0$ and $f_1$
\begin{itemize}
\item Childs, Jao, and Soukharev -- compute $*$ operator in subexponential time
\end{itemize}
\item Solving HSP (using quantum computer)
\begin{itemize}
\item Kuperberg's algorithm -- faster running time, superpolynomial space
\item Regev's algorithm -- slower, but polynomial space
\item Childs, Jao, Soukharev -- fill in the gaps
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Conclusions}
\begin{itemize}
\item Assuming GRH, there is a subexpontial quantum algorithm to compute isogenies.
\item With classical computers, isogeny problem is "easier" $(p^{1/4}$ to $p^{1/2}$) than discrete log, but situation is reversed with quantum computers.
\item Actually, input to algorithm is End($E$), or $\mathcal{O}$.
\begin{itemize}
\item This is part of public parameters for all proposed isogeny based cryptosystems.
\end{itemize}
\item For arbitrary, ordinary curves, there is a subexponential (quantum) algorithm to compute End($E$), assuming the GRH.
\end{itemize}
\end{frame}

\begin{frame}{Last words?}
\begin{itemize}
\item {\footnotesize Authors conclude: "Since isogeny-based cryptosystems already perform
poorly at moderate security levels, any improved attacks such as ours would seem to
disqualify such systems from consideration in a post-quantum world."}
\item {\footnotesize Stolbunov: "First of all, it is not clear whether the superpolynomial quantum attack of
Childs, Jao and Soukharev will pose a realistic threat. The attack requires
$O(2^{6\sqrt {s \log(s)}})$ quantum gates. Physicists are in doubt about the possibility of
large-scale quantum computations, because of errors introduced by the quantum decoherence. If
no key length adjustment will be needed to protect against the named
attack, then the isogeny-based schemes will offer, in general, shorter keys and more efficient
bandwidth usage, as compared to other quantum-resistant hard problems. But this
will come at a cost of lower operational speeds."} 
\end{itemize}
\end{frame}

\begin{frame}{The Second Paper (Jao, de Feo)}
\begin{itemize}
\item Flaws of previous system:
\begin{itemize}
\item Not very efficient (229s for 128 bit security)
\item Subexponential attack
\end{itemize}
\vspace{20 pt}
\item New supersingular isogeny-based cryptosytem
\begin{itemize}
\item Way more efficient (60ms for 128 bit security)
\item No subexponential attack known
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Supersingular Curves}
\begin{itemize}
\item Recall $E$ is supersingular if $\#(E(\Fp))=p+1-t$, and $p|t$.
\item Supersingular curves are rare.
\item Endomorphism ring of $E$ is an order in quaternion algebra.
\item In particular, End($E$) is not commutative.
\item All supersingular curves can be defined over $\mathbb{F}_{p^2}$.
\item Can represent ker$(\phi)$ efficiently over $\mathbb{F}_{p^2}$.  This is not possible for ordinary curves.
\begin{itemize}
\item This fact leads to increase in speed.
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Supersingular Graphs}
\begin{itemize}
\item $\ell$-isogeny graph is $\ell+1$-regular (assuming $\ell \nodiv p$).
\item The graph is an expander graph, or Ramanujan graph.
\item Supersingular isogeny graph used for Charles, Goren, Lauter's hash function.
\vspace{10 pt}
\item Let $p=\ell_A^{e_A} \ell_B^{e_B}f \pm 1$ be prime, for small primes $\ell_A, \ell_B$.
\item Usually this is bad, but we don't need discrete log to be hard.
\end{itemize}
\end{frame}

\begin{frame}{Key Exchange}
\begin{figure}
\includegraphics[width = 3.5 in]{commisog.pdf}
\end{figure}
\vspace{-15 pt}
\begin{itemize}
\item Let $P_A,Q_A$  be generators of $E[\ell_A^{e_a}]$, and analogously for $P_B,Q_B$.
\item Alice chooses random $m_A,n_A$ and computes $\phi_A:E \to E_A$ with kernel $m_AP_A+n_AQ_A$.
\item Alice sends $E_A$,$\phi_A(P_B)$ and $\phi_A(Q_B)$ to Bob. Bob does similarly.
\item Alice computes $\phi'_A:E_B \to E_{AB}$ with kernel $m_A\phi_B(P_A)+n_A\phi_B(Q_A)$.  Bob does similarly.
\item The key is $j(E_{AB})$.
\end{itemize}
\end{frame}

\begin{frame}{Speed and Security}
\begin{itemize}
\item (We skip description of encryption system)
\item Best general algorithm to compute isogenies between supersingular curves is $O\left(\sqrt{p} \log^2{p}\right)$.
\item There is a classical "claw" attack with $O\left( \sqrt[4]{p}\right)$, and a quantum "claw" attack with $O\left( \sqrt[6]{p}\right)$
\item Benchmarks (on desktop):
\end{itemize}
\vspace{5 pt}
\begin{center}
\begin{tabular}{ |l | c | c | c |}
\hline
Security & 85 bits & 128 bits & 170 bits \\
  \hline                        
Time (ms) &  28 & 66& 122 \\
   \hline  
\end{tabular}
\end{center}
\end{frame}

\begin{frame}{Summary}
\begin{itemize}
\item Isogeny-based cryptosystems.
\item Subexponential attack on isogenies between elliptic curves.
\item Jao, de Feo propose new supersingular cryptosytem
\begin{itemize}
\item No quantum attacks known (yet)
\item Efficient
\end{itemize}
\vspace{5 pt}
\item Conclusion:  wait and see.
\end{itemize}
\end{frame}

\end{document}