\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[utf8]{inputenc}

\begin{document}

\section{ECC Summer School 2015}
\subsection{Intro - Software and Hardware implementation of Elliptic Curve Cryptography}
Presentation by Jérémie Detrey.
Reminders on elliptic curves over finite fields, associated operations, ECDH and ElGamal. \newline
Jérémie then states the design goals of ECC implementations: efficient and secure. 

Efficiency can have multiple meanings. Does it refer to:
\begin{itemize}
	\item fast? $\to$ low latency or high throughput?
	\item small? $\to$ low memory / code / silicon usage?
	\item low power? ... or low energy?
\end{itemize}
Constraints are going to depend to the application and target platform.

The other design goal was security, but secure against which attack:
\begin{itemize}
	\item protocol attacks? (FREAK, LogJam, etc) [More in N. Heninger's talk]
	\item curve attacks? (weak curves, twist security, etc.)
	\item timing attacks? [More in P. Schwabe's talk]
	\item fault attacks? [More in J. Krämer's talk]
	\item cache attacks?
	\item branch-prediction attacks?
	\item power or electromagnetic analysis?
\end{itemize}

A list of possible target platforms is enumerated to highlight the discrepancy in resources between them.

The layer of ECC implementations are usually: 
\begin{itemize}
	\item protocol (OpenPGP, TLS, SSH, etc)
	\item cryptographic primitives (ECDH, ECDSA, etc)
	\item scalar multiplication
	\item elliptic curve arithmetic (point addition, point doubling, etc.)
	\item finite field arithmetic (addition, multiplication, inversion ...)
	\item native integer arithmetic (CPU instruction set)
\end{itemize}

For hardware implementations, there are additional layers:
\begin{itemize}
	\item logic circuits (registers, multiplexers, adders, etc.)
	\item logic gates (NOT, NAND, etc.) and wires
	\item transistors
\end{itemize}

All (top) layers might lead to critical vulnerabilities if poorly implemented! ECC is no more secure than its weakest link.

Jérémie concludes introduction with some references. Most books are already quite old. He suggests to read proceedings of recent crypto conferences such as CHES.

Elliptic curve points multiplication methods are then covered (Double-and-add, windowed method, wNAF method, GLV curves ...). The double-and-add algorithm is easily vulnerable to timing analysis (by revealing the hamming weight of secret k) and a power analysis will leak bits of k. An counter-measure to this attack could be to "double-and-add-always" but this is still vulnerable to fault-attacks. A better alternative is the Montgomery ladder since it has the following properties: 
\begin{itemize}
	\item performs one addition and one doubling at each step
	\item ensure that both results are used in the next step
	\item loop invariant: $T_1$ = $T_0$ + $P$ (See slides)
\end{itemize}

But the conditional branches depend on the value of a secret bit $k_i$. Hence, it might be vulnerable to branch prediction attacks. We can compute indices for $T_0$ and $T_1$ from $k_i$? Issue is that memory access to $T_0$ or $T_1$ depend on secret bit $k_i$, hence might be vulnerable to cache attacks.

Solution: use bit masking to avoid secret-dependent memory access patterns.

\subsection{The group of rational points of an elliptic curve over a finite field}
Presentation by Damien Robert. He starts his presentation by defining an elliptic curves over complex numbers and defining classes of isomorphisms of elliptic curves. Two elliptic curves $E$ and $E'$ are isomorphic over $\bar{k} \iff j_{E} = j{\bar{E}}$ where $j$ is the $j-invariant$.

A twist of an elliptic curve $E/k$ is an elliptic curve $E'/k$ isomorphic to $E$ over $\bar{k}$ but not over $k$.

Why look at the complex numbers? For cryptography we work with elliptic curves over finite fields. Everything that is true over $\mathbb{C}$ is true over other fields except when it is not true (non algebraically closed fields, characteristic $p$ ...). Example: "there are $n^2$ points of $N$-torsion."
How can we transfer results from $\mathbb{C}$ to other fields?
Damien then goes back to $\mathbb{C}$ and defines the Weil pairing over $\mathbb{C}$.
For more notes on this session, refer to slides.

\subsection{Algorithms for discrete logarithms in finite fields and elliptic curves}
Presentation by Emmanuel Thomé. Introduction to ECDLP. This presentation does not address here the DH-related problems, but really the computation of DL.
\subsubsection{Hardness}
What does it mean for:
\begin{itemize}
	\item DLP to be hard on EC
	\item DLP to be moderately hard on finite fields
	\item DLP to be easy on small characteristic finite fields.
\end{itemize}

We want the cost of computing DL by most efficient
means known to grow fast.

So, what groups shall we avoid?
\begin{itemize}
	\item Easy DL: $(\mathbb{Z}/N\mathbb{Z}, +)$
	\item Not-so-hard DL: finite fields, curves of very large genus, class
groups of number fields
	\item Hard DL: elliptic curves, curves of genus 2
\end{itemize}

Claim: since finite fields are not-so-hard, why not ditch them and just use EC hardness?

Why finite fields are still interesting 
\begin{itemize}
	\item Some protocols prefer them
	\item Pairings! Some cryptographic protocols use pairings:
\[
	e: \mathbb{G} \times \mathbb{G} \to K^\star
\]
	\item Tricks with subgroups of the multiplicative group. \begin{itemize}
		\item we are not necessarily interested in the DLP in the whole
multiplicative group per se
		\item we shall not be annoyed by some uninteresting prime factors
behaving oddly
		\item DL modulo small primes can be handled differently anyway 
	\end{itemize}
\end{itemize}

Known generic solutions to DLP. All of the following algorithms are exponential in the bit-size of G:
\begin{itemize}
	\item Enumeration
	\item Baby-step–Giant-step
	\item Pollard $\rho$
	\item Parallel collision search
\end{itemize}

In Nechaev-Shoup [Nec94,Sho97], lower-bound for a generic (black-box) group $G$ with $n = \sqrt{G}$, no discrete logarithm algorithm succeeds in time less than $\mathcal{O}(\sqrt(n))$.

As it turns out, finite fields have faster DLP algorithms than generic groups. First algorithm of this kind: Adleman [Adl79], based on the combination of congruences idea. \newline
Smoothness: a polynomial of degree at most $n$ is $k$-smooth if all its irreducible factors have degree at most $k$. The smoothness is a construction kit situation. Works fine for finite fields, much less for EC. 

Overview of Adleman's algorithm (See slides/online). Thanks to the smoothness probability, we can find an optimal choice for the B factor. The overall complexity of Adleman's algorithm is sub-exponential complexity, L(1/2). Consequence, the key size is roughly the square of time.

\subsubsection{L(1/3) Algorithms}

What makes Adleman's algorithm so slow?

\begin{itemize}
	\item Elements created as $g^r \pmod p$ are as large as $p$
	\item For computing individual logarithms, we have no way to take advantage of the fact that $h$ might perhaps have not-so-large bit size.
\end{itemize}

If we could take advantage of $h$ might have a not-so-large bit size, we might imagine a recursive procedure. Getting to the NFS-DL via the FFS.

Outline of algorithm: 
\begin{itemize}
	\item Do the setup. Choose a factor base bound $B$ 
	\item Relation search. Pick pairs $a, b$ for coprime integers $a$ and $b$. Expect $a - bm$ to be a smooth integer. Expect also the ideal $(a-b\alpha)$ to be smooth. Compute Schirokauer maps. Do linear algebra to compute virtual logarithms of factor base elements. Compute individual logarithms.
\end{itemize}

Analysis of runtime of NFS gives $L_p[1/3]$ where $p$ is a prime. Not all $p$ are born equal. Some exceptionally easy $p$ conspicuous. But disguising an easy $p$ as an honest random-looking $p$ is easy: pick $f$ and $g$ to our liking; publish $p$ = Res($f$ , $g$ ). Improvements since NFS. The complexity depends much on how $n$ compares to log $p$ for $\mathbb{F}_{p^n}$.

Covers $L(1/3)$ on large genus curves.

\subsubsection{Benefits of Sieving}
\begin{itemize}
	\item Forced factor in the norm improves the smoothness probability
	\item Reduced lattice basis limits the expense of this constraint on the size of $(a,b)$.
	\item Sieved areas are smaller, each is typically manageable on a single node.
	\item Special-q [DH84] provide an easy division (reduces sieving space), with (almost) stable yield. (Gives reasonable expectations of time computation will take)
\end{itemize}

Implementation tricks such as sieving by vectors and bucket sieving can improve performance.

Black box algorithms favorable for performance reasons. State of the art:
\begin{itemize}
	\item Block Wiedemann algorithm: offers more distribution opportunities
	\item Block Lanczos algorithm: needs fewer matrix operations
\end{itemize}

Current record in $\mathbb{F}_p$: Bouvier, Gaudry, Imbert, Jeljeli, T.: 180dd (600 bits), 2014\newline
Records over binary fields: \begin{itemize}
	\item Record for $\mathbb{F}_{2^p}$ : 1279 bits [Kleinjung14]
	\item Record for $\mathbb{F}_{2^n}$ : 9234 bits (9234 = 2 · 35 · 19) [GKZ14]
\end{itemize}

\subsubsection{Quasi-polynomial DLP in small characteristic} [See Slides]

Conclusion: New algorithm Quasi-polynomial complexity. Relies on heuristic, experimentally checked. RIP small characteristic pairings. This does not affect RSA, nor large characteristic DLP.

\end{document}
