%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[mathserif,a4paper]{beamer}
%\documentclass[a4paper]{article}
%\usepackage[envcountsect,noxcolor]{beamerarticle}
%\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\DeclareUnicodeCharacter{00A0}{~}
% Beamer theme:
\usetheme{Goettingen}
%\usecolortheme{albatross}
%\usecolortheme{lily}
%\setbeamercovered{transparent}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
%
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{matrix,arrows,snakes,calc}
%
\newcommand{\itempoint}{\strut\hbox{\color{beamerstructure}\donotcoloroutermaths$\blacktriangleright$}\nobreak\hskip.5em plus.5em\relax}
\renewcommand{\thefootnote}{\textdagger}
\DeclareMathSymbol{\lquote}{\mathopen}{operators}{"5C}
\DeclareMathSymbol{\rquote}{\mathclose}{operators}{"22}
\newcommand{\rang}{\mathop\mathrm{rg}\nolimits}
\newcommand{\Vect}{\mathop\mathrm{Vect}\nolimits}
\newcommand{\vol}{\mathop\mathrm{vol}\nolimits}
\newcommand{\covol}{\mathop\mathrm{covol}\nolimits}
\newcommand{\transp}{\mathop\mathrm{tr}\nolimits}
\newcommand{\proj}{\mathop\mathrm{proj}\nolimits}
\newcommand{\dist}{\mathop\mathrm{dist}\nolimits}
%
%
%
\title{Réseaux euclidiens et cryptographie}
\subtitle{Journées Télécom-UPS\\« Le numérique pour tous »}
\author[David Madore]{David A. Madore\\
{\footnotesize Télécom ParisTech}\\
\texttt{david.madore@enst.fr}}
\date{29 mai 2015}
\mode<presentation>{%
\beamertemplatenavigationsymbolsempty
\usenavigationsymbolstemplate{\vbox{\hbox{\footnotesize\hyperlinkslideprev{$\leftarrow$}\insertframenumber/\inserttotalframenumber\hyperlinkslidenext{$\rightarrow$}}}}
}
\setbeamercolor{myhighlight}{fg=black,bg=white!90!green}
\begin{document}
\mode<article>{\maketitle}
%
\frame{\titlepage}
%
\section*{Plan}
\begin{frame}
\frametitle{Plan}
\tableofcontents
\end{frame}
%
\section{Généralités sur les réseaux euclidiens}
\begin{frame}
\frametitle{Réseaux euclidiens : définition}

\begin{beamercolorbox}[sep=.5em]{myhighlight}
\itempoint Un \textbf{réseau} de $\mathbb{R}^m$ est un sous-groupe
(additif) discret $L$ de l'espace euclidien $\mathbb{R}^m$.
\end{beamercolorbox}

\smallskip

Un tel sous-groupe est nécessairement isomorphe à $\mathbb{Z}^n$
(où $n\leq m$) comme groupe abélien : il existe $b_1,\ldots,b_n \in L$
tels que $L = \mathbb{Z}b_1 \oplus \cdots \oplus \mathbb{Z}b_n$.

\smallskip

De plus, $b_1,\ldots,b_n$ sont $\mathbb{R}$-libres (=linéairement
indép\textsuperscript{ts}).

\smallskip

On dit qu'ils sont une \textbf{base} de $L$, et que $n$ est le
\textbf{rang} de $L$.

\bigskip

{\footnotesize Définition équivalente :\par}

\begin{beamercolorbox}[sep=.5em]{myhighlight}
\itempoint Un \textbf{réseau} de $\mathbb{R}^m$ est un $\mathcal{L}(B)
:= \{u B : u \in \mathbb{Z}^n\}$ où $B \in \mathbb{R}^{n\times m}$ est
une matrice de rang $n$.
\end{beamercolorbox}

($B$ est la matrice dont les $b_i$ sont les \underline{lignes}.)

\bigskip

\itempoint On suppose souvent $m=n$ (réseau de \emph{rang plein}),
quitte à se placer dans $\Vect_{\mathbb{R}}(L) = \mathbb{R}b_1 \oplus
\cdots \oplus \mathbb{R}b_n$.

\end{frame}
%
\begin{frame}
\frametitle{Exemples}

Les deux réseaux de rang $2$ admettant le plus grand groupe de
symétries sont {\footnotesize (à similitude près)} :

\smallskip

\begin{tabular*}{\textwidth}{c@{\extracolsep{\fill}}c}
\begin{tikzpicture}
\clip[draw,use as bounding box](-2cm,-1.5cm) rectangle (2cm,1.5cm);
\begin{scope}[scale=0.6,circle,every node/.style={fill=black,inner sep=1pt}]
\path[fill=white!80!purple] (0cm,0cm) -- (1cm,0cm) -- (1cm,1cm) -- (0cm,1cm) -- cycle;
\node at (-3cm,-2cm) {};
\node at (-2cm,-2cm) {};
\node at (-1cm,-2cm) {};
\node at (0cm,-2cm) {};
\node at (1cm,-2cm) {};
\node at (2cm,-2cm) {};
\node at (3cm,-2cm) {};
\node at (-3cm,-1cm) {};
\node at (-2cm,-1cm) {};
\node at (-1cm,-1cm) {};
\node at (0cm,-1cm) {};
\node at (1cm,-1cm) {};
\node at (2cm,-1cm) {};
\node at (3cm,-1cm) {};
\node at (-3cm,0cm) {};
\node at (-2cm,0cm) {};
\node at (-1cm,0cm) {};
\node[fill=red] at (0cm,0cm) {};
\node at (1cm,0cm) {};
\node at (2cm,0cm) {};
\node at (3cm,0cm) {};
\node at (-3cm,1cm) {};
\node at (-2cm,1cm) {};
\node at (-1cm,1cm) {};
\node at (0cm,1cm) {};
\node at (1cm,1cm) {};
\node at (2cm,1cm) {};
\node at (3cm,1cm) {};
\node at (-3cm,2cm) {};
\node at (-2cm,2cm) {};
\node at (-1cm,2cm) {};
\node at (0cm,2cm) {};
\node at (1cm,2cm) {};
\node at (2cm,2cm) {};
\node at (3cm,2cm) {};
\draw[->,purple] (0cm,0cm) -- (1cm,0cm);
\draw[->,purple] (0cm,0cm) -- (0cm,1cm);
\end{scope}
\end{tikzpicture}
&
\begin{tikzpicture}
\clip[draw,use as bounding box](-2cm,-1.5cm) rectangle (2cm,1.5cm);
\begin{scope}[scale=0.645,circle,every node/.style={fill=black,inner sep=1pt}]
\path[fill=white!80!purple] (0cm,0cm) -- (1cm,0cm) -- (0.5cm,0.866cm) -- (-0.5cm,0.866cm) -- cycle;
\node at (-3cm,-1.732cm) {};
\node at (-2cm,-1.732cm) {};
\node at (-1cm,-1.732cm) {};
\node at (0cm,-1.732cm) {};
\node at (1cm,-1.732cm) {};
\node at (2cm,-1.732cm) {};
\node at (3cm,-1.732cm) {};
\node at (-2.5cm,-0.866cm) {};
\node at (-1.5cm,-0.866cm) {};
\node at (-0.5cm,-0.866cm) {};
\node at (0.5cm,-0.866cm) {};
\node at (1.5cm,-0.866cm) {};
\node at (2.5cm,-0.866cm) {};
\node at (-3cm,0cm) {};
\node at (-2cm,0cm) {};
\node at (-1cm,0cm) {};
\node[fill=red] at (0cm,0cm) {};
\node at (1cm,0cm) {};
\node at (2cm,0cm) {};
\node at (3cm,0cm) {};
\node at (-2.5cm,0.866cm) {};
\node at (-1.5cm,0.866cm) {};
\node at (-0.5cm,0.866cm) {};
\node at (0.5cm,0.866cm) {};
\node at (1.5cm,0.866cm) {};
\node at (2.5cm,0.866cm) {};
\node at (-3cm,1.732cm) {};
\node at (-2cm,1.732cm) {};
\node at (-1cm,1.732cm) {};
\node at (0cm,1.732cm) {};
\node at (1cm,1.732cm) {};
\node at (2cm,1.732cm) {};
\node at (3cm,1.732cm) {};
\draw[->,purple] (0cm,0cm) -- (1cm,0cm);
\draw[->,purple] (0cm,0cm) -- (-0.5cm,0.866cm);
\end{scope}
\end{tikzpicture}
\\
$(A_1)^2$
&
$A_2$
\\
\tiny $\mathbb{Z}^2 \subseteq \mathbb{R}^2$
&
\tiny $\{(x,y,z)\in\mathbb{Z}^3 : x+y+z=0\} \subseteq \mathbb{R}^3$
\end{tabular*}

\end{frame}
%
\begin{frame}
\frametitle{Bases et parallélotopes fondamentaux}

{\footnotesize Soit $\mathcal{L}(B) = \{u B : u \in \mathbb{Z}^n\}
  \subseteq \mathbb{R}^m$ (où $\rang B = n$).\par}

\medskip

\itempoint $\mathcal{P}(B) := \{u B : u\in [0;1[^n\}$ s'appelle
    \textbf{parallélotope fondamental} associé à la base $B$.

\medskip

\begin{beamercolorbox}[sep=.5em]{myhighlight}
\itempoint On a $\mathcal{L}(B) = \mathcal{L}(B')$ ssi $B' = UB$ où $U \in
\mathit{GL}_n(\mathbb{Z})$.
\end{beamercolorbox}

Ici, $\mathit{GL}_n(\mathbb{Z})$ est l'ensemble des matrices $n\times
n$ à coefficients entiers, de déterminant $\pm 1$
(\textbf{unimodulaires}).

\smallskip

Dès que $n>1$, un réseau admet une infinité de bases.

\bigskip

{\footnotesize On peut voir l'ensemble des réseaux de rang plein dans
  $\mathbb{R}^n$ comme l'ensemble quotient $\mathit{GL}_n(\mathbb{Z})
  \backslash \mathit{GL}_n(\mathbb{R})$. \par}

\bigskip

\itempoint $\vol(\mathcal{P}(B)) =: \covol(\mathcal{L}(B)) =
|\det(B)|$ (lorsque $m=n$) : volume du parallélogramme fondamental :
\textbf{(co)volume} ou \textbf{déterminant} du réseau.  Ne dépend pas
de $B$ !

\end{frame}
%
\begin{frame}
\frametitle{Toutes les bases ne se valent pas}

Certaines bases sont plus « agréables » que d'autres :

\smallskip

\begin{tabular*}{\textwidth}{c@{\extracolsep{\fill}}c}
\begin{tikzpicture}
\clip[draw,use as bounding box](-2cm,-1.5cm) rectangle (2cm,1.5cm);
\begin{scope}[scale=0.548,circle,every node/.style={fill=black,inner sep=1pt}]
\path[fill=white!80!purple] (-2.6cm,-2.4cm) -- (-1.6cm,-2.4cm) -- (-1.8cm,-1.2cm) -- (-2.8cm,-1.2cm) -- cycle;
\node at (-3.6cm,-2.4cm) {};
\node[fill=red] at (-2.6cm,-2.4cm) {};
\node at (-1.6cm,-2.4cm) {};
\node at (-0.6cm,-2.4cm) {};
\node at (0.4cm,-2.4cm) {};
\node at (1.4cm,-2.4cm) {};
\node at (2.4cm,-2.4cm) {};
\node at (3.4cm,-2.4cm) {};
\node at (-3.8cm,-1.2cm) {};
\node at (-2.8cm,-1.2cm) {};
\node at (-1.8cm,-1.2cm) {};
\node at (-0.8cm,-1.2cm) {};
\node at (0.2cm,-1.2cm) {};
\node at (1.2cm,-1.2cm) {};
\node at (2.2cm,-1.2cm) {};
\node at (3.2cm,-1.2cm) {};
\node at (-4cm,0cm) {};
\node at (-3cm,0cm) {};
\node at (-2cm,0cm) {};
\node at (-1cm,0cm) {};
\node at (0cm,0cm) {};
\node at (1cm,0cm) {};
\node at (2cm,0cm) {};
\node at (3cm,0cm) {};
\node at (4cm,0cm) {};
\node at (-3.2cm,1.2cm) {};
\node at (-2.2cm,1.2cm) {};
\node at (-1.2cm,1.2cm) {};
\node at (-0.2cm,1.2cm) {};
\node at (0.8cm,1.2cm) {};
\node at (1.8cm,1.2cm) {};
\node at (2.8cm,1.2cm) {};
\node at (3.8cm,1.2cm) {};
\node at (-3.4cm,2.4cm) {};
\node at (-2.4cm,2.4cm) {};
\node at (-1.4cm,2.4cm) {};
\node at (-0.4cm,2.4cm) {};
\node at (0.6cm,2.4cm) {};
\node at (1.6cm,2.4cm) {};
\node at (2.6cm,2.4cm) {};
\node at (3.6cm,2.4cm) {};
\draw[->,purple] (-2.6cm,-2.4cm) -- (-1.6cm,-2.4cm);
\draw[->,purple] (-2.6cm,-2.4cm) -- (-2.8cm,-1.2cm);
\end{scope}
\end{tikzpicture}
&
\begin{tikzpicture}
\clip[draw,use as bounding box](-2cm,-1.5cm) rectangle (2cm,1.5cm);
\begin{scope}[scale=0.548,circle,every node/.style={fill=black,inner sep=1pt}]
\path[fill=white!80!purple] (-2.6cm,-2.4cm) -- (-0.8cm,-1.2cm) -- (1.8cm,1.2cm) -- (0cm,0cm) -- cycle;
\node at (-3.6cm,-2.4cm) {};
\node[fill=red] at (-2.6cm,-2.4cm) {};
\node at (-1.6cm,-2.4cm) {};
\node at (-0.6cm,-2.4cm) {};
\node at (0.4cm,-2.4cm) {};
\node at (1.4cm,-2.4cm) {};
\node at (2.4cm,-2.4cm) {};
\node at (3.4cm,-2.4cm) {};
\node at (-3.8cm,-1.2cm) {};
\node at (-2.8cm,-1.2cm) {};
\node at (-1.8cm,-1.2cm) {};
\node at (-0.8cm,-1.2cm) {};
\node at (0.2cm,-1.2cm) {};
\node at (1.2cm,-1.2cm) {};
\node at (2.2cm,-1.2cm) {};
\node at (3.2cm,-1.2cm) {};
\node at (-4cm,0cm) {};
\node at (-3cm,0cm) {};
\node at (-2cm,0cm) {};
\node at (-1cm,0cm) {};
\node at (0cm,0cm) {};
\node at (1cm,0cm) {};
\node at (2cm,0cm) {};
\node at (3cm,0cm) {};
\node at (4cm,0cm) {};
\node at (-3.2cm,1.2cm) {};
\node at (-2.2cm,1.2cm) {};
\node at (-1.2cm,1.2cm) {};
\node at (-0.2cm,1.2cm) {};
\node at (0.8cm,1.2cm) {};
\node at (1.8cm,1.2cm) {};
\node at (2.8cm,1.2cm) {};
\node at (3.8cm,1.2cm) {};
\node at (-3.4cm,2.4cm) {};
\node at (-2.4cm,2.4cm) {};
\node at (-1.4cm,2.4cm) {};
\node at (-0.4cm,2.4cm) {};
\node at (0.6cm,2.4cm) {};
\node at (1.6cm,2.4cm) {};
\node at (2.6cm,2.4cm) {};
\node at (3.6cm,2.4cm) {};
\draw[->,purple] (-2.6cm,-2.4cm) -- (-0.8cm,-1.2cm);
\draw[->,purple] (-2.6cm,-2.4cm) -- (0cm,0cm);
\end{scope}
\end{tikzpicture}
\\
« Bonne » base
&
Moins « bonne » base
\end{tabular*}

\smallskip

{\footnotesize Les deux parallélogrammes fondamentaux dessinés ont la
  même aire, mais pas la même forme / la même longueur des côtés.\par}

\medskip

{\footnotesize « Bonne » $\approx$ constituée de petits vecteurs.\par}

\medskip

\textbf{Thèmes :} Comment construire de « bonnes » bases à partir de
« mauvaises » ?  (Par des opérations élémentaires entières sur les
lignes de $B$.)  Comment exploiter la \alert{difficulté} de ce
problème ?

\end{frame}
%
\begin{frame}
\frametitle{Similitudes}

{\footnotesize Soit $\mathcal{L}(B) = \{u B : u \in \mathbb{Z}^n\}
  \subseteq \mathbb{R}^m$ (où $\rang B = n$).\par}

\medskip

\itempoint Si $t \in \mathbb{R}^\times$, on a $t\cdot \mathcal{L}(B)
= \mathcal{L}(t B)$ (\emph{homothétie}).\\Multiplie le covolume par
$t^n$.

\itempoint Si $\mathit{\Omega} \in \mathit{O}_m$, on a $\mathcal{L}(B)
\cdot \mathit{\Omega} = \mathcal{L}(B \mathit{\Omega})$
(\emph{isométrie}).\\Ne change pas le covolume.

{\footnotesize Si $\mathcal{L}(B) \cdot \mathit{\Omega} =
  \mathcal{L}(B)$, on dit que $\mathit{\Omega}$ est une
  \textbf{symétrie} de $\mathcal{L}(B)$.\par}

\smallskip

On identifie souvent deux réseaux homothétiques, isométriques, ou les
deux (semblables).\\Ceci permet de \textbf{normaliser} $\covol(L) =
1$.

\bigskip

{\footnotesize On peut considérer $\mathit{SL}^\pm_n(\mathbb{R}) /
  \mathit{O}_n$ comme l'espace des \emph{formes de parallélotopes} de
  dimension $n$ [espace riemannien symétrique], et
  $\mathit{GL}_n(\mathbb{Z}) \backslash \mathit{SL}^\pm_n(\mathbb{R})
  / \mathit{O}_n$ comme l'espace des \emph{formes de réseaux} de rang
  plein.\par}

\bigskip

\itempoint\textbf{Matrice de Gram :} $G := B B^{\transp}$ soit $G_{ij}
= b_i \cdot b_j$, invariante par isométrie ($B \mathit{\Omega} (B
\mathit{\Omega})^{\transp} = B B^{\transp}$).

\end{frame}
%
\begin{frame}
\frametitle{Matrice de Gram}

{\footnotesize Soit $\mathcal{L}(B) = \{u B : u \in \mathbb{Z}^n\}
  \subseteq \mathbb{R}^m$ (où $\rang B = n$).\par}

\medskip

\textbf{Matrice de Gram :} $G := B B^{\transp}$ soit $G_{ij} = b_i
\cdot b_j$.

\medskip

\itempoint \alert{Invariante par isométrie} {\footnotesize ($B
  \mathit{\Omega} (B \mathit{\Omega})^{\transp} = B B^{\transp}$ si
  $\mathit{\Omega} \in \mathit{O}_m$)}.

\medskip

\itempoint Est la matrice de la forme quadratique sur $\mathbb{Z}^n$
définie par $q(u) = \|u B\|^2$ (norme euclidienne transportée au
réseau), donc \alert{définie positive}.  {\footnotesize
  ($\Rightarrow$ Lien avec les f.q. sur les entiers.)}

\medskip

\itempoint Vérifie $\det(G) = \covol(L)^2$ (\textbf{discriminant} de
$L = \mathcal{L}(B)$).

{\footnotesize En effet, $\det(G) = \det(B)^2$ est évident
  si $m=n$.\par}

\medskip

\itempoint Réciproquement, si $G$ est définie positive, on peut écrire
$G = B B^{\transp}$ pour $B \in \mathit{GL}_n(\mathbb{R})$
(conséquence de Cholesky ou du théorème spectral), et $B$ est unique à
isométrie près.

\medskip

{\footnotesize L'espace $\mathit{SL}^\pm_n(\mathbb{R}) / \mathit{O}_n$
  s'identifie donc à l'ensemble des matrices définies positives de
  déterminant $1$, et $\mathit{GL}_n(\mathbb{Z}) \backslash
  \mathit{SL}^\pm_n(\mathbb{R}) / \mathit{O}_n$ à l'ensemble des
  formes quadratiques définies positives sur un $\mathbb{Z}$-module de
  rang $n$. \par}

\end{frame}
%
\begin{frame}
\frametitle{Orthogonalisation de Gram-Schmidt}

\itempoint Si $b_1,\ldots,b_n \in \mathbb{R}^m$ sont
$\mathbb{R}$-libres, on définit par récurrence $b^\star_i := b_i -
\sum_{j<i} \mu_{i,j}\, b^\star_j$\quad où\quad $\mu_{i,j} :=
(b_i \cdot b^\star_j)/\|b^\star_j\|^2$\\ (i.e., $b^\star_i =
\proj_{\Vect(b_j:j<i)^{\perp}}(b_i)$).

\medskip

Les $(b^\star_i)_{i\leq s}$ sont donc une base \alert{orthogonale}
de $\Vect(b^\star_i : i\leq s) = \Vect(b_i : i\leq s)$.

\bigskip

\itempoint Formulation matricielle (pour $m=n$) : $B = MDV$ avec $M$
triangulaire inférieure de diagonale $1$ (soit : $M_{ij} = \mu_{i,j}$
si $j<i$, $1$ si $j=i$, et $0$ si $j>i$), $D$ diagonale de diagonale
$\|b^\star_i\|$, et $V$ orthogonale.

\medskip

En particulier, $|\det(B)| = \det D = \prod_{i=1}^n \|b^\star_i\|$.

\bigskip

\itempoint Dépend de l'ordre : si on permute $b_i \leftrightarrow
b_{i+1}$, alors $(b_i^\star, b_{i+1}^\star)$ devient $(b_{i+1}^\star +
\mu_{i+1,i}\, b_i^\star, \penalty0\; \frac{\|b_{i+1}^\star\|^2\,
  b_i^\star - \mu_{i+1,i}\, \|b_i^\star\|^2\,
  b_{i+1}^\star}{\|b_{i+1}^\star\|^2 + \mu_{i+1,i}^2\,
  \|b_i^\star\|^2})$.

\end{frame}
%
\begin{frame}
\frametitle{Gram-Schmidt (suite)}

Calcul de l'aire d'un parallélogramme :

\smallskip

\begin{tabular*}{\textwidth}{c@{\extracolsep{\fill}}c}
\begin{tikzpicture}
\clip[draw,use as bounding box](-2cm,-1.5cm) rectangle (2cm,1.5cm);
\begin{scope}[scale=1.096,circle,every node/.style={fill=black,inner sep=1pt}]
\path[fill=white!80!purple] (0cm,0cm) -- (1cm,0cm) -- (0.8cm,1.2cm) -- (-0.2cm,1.2cm) -- cycle;
\node at (-2.8cm,-1.2cm) {};
\node at (-1.8cm,-1.2cm) {};
\node at (-0.8cm,-1.2cm) {};
\node at (0.2cm,-1.2cm) {};
\node at (1.2cm,-1.2cm) {};
\node at (2.2cm,-1.2cm) {};
\node at (-3cm,0cm) {};
\node at (-2cm,0cm) {};
\node at (-1cm,0cm) {};
\node[fill=red] at (0cm,0cm) {};
\node at (1cm,0cm) {};
\node at (2cm,0cm) {};
\node at (3cm,0cm) {};
\node at (-2.2cm,1.2cm) {};
\node at (-1.2cm,1.2cm) {};
\node at (-0.2cm,1.2cm) {};
\node at (0.8cm,1.2cm) {};
\node at (1.8cm,1.2cm) {};
\node at (2.8cm,1.2cm) {};
\draw[->,purple] (0cm,0cm) -- (1cm,0cm);
\draw[->,purple] (0cm,0cm) -- (-0.2cm,1.2cm);
\end{scope}
\end{tikzpicture}
&
\begin{tikzpicture}
\clip[draw,use as bounding box](-2cm,-1.5cm) rectangle (2cm,1.5cm);
\begin{scope}[scale=1.096,circle,every node/.style={fill=black,inner sep=1pt}]
\path[fill=white!80!orange] (0cm,0cm) -- (1cm,0cm) -- (1cm,1.2cm) -- (0cm,1.2cm) -- cycle;
\node at (-2.8cm,-1.2cm) {};
\node at (-1.8cm,-1.2cm) {};
\node at (-0.8cm,-1.2cm) {};
\node at (0.2cm,-1.2cm) {};
\node at (1.2cm,-1.2cm) {};
\node at (2.2cm,-1.2cm) {};
\node at (-3cm,0cm) {};
\node at (-2cm,0cm) {};
\node at (-1cm,0cm) {};
\node[fill=red] at (0cm,0cm) {};
\node at (1cm,0cm) {};
\node at (2cm,0cm) {};
\node at (3cm,0cm) {};
\node at (-2.2cm,1.2cm) {};
\node at (-1.2cm,1.2cm) {};
\node at (-0.2cm,1.2cm) {};
\node at (0.8cm,1.2cm) {};
\node at (1.8cm,1.2cm) {};
\node at (2.8cm,1.2cm) {};
\draw[->,orange] (0cm,0cm) -- (1cm,0cm);
\draw[->,orange] (0cm,0cm) -- (0cm,1.2cm);
\end{scope}
\end{tikzpicture}
\\
$(b_1,b_2)$
&
$(b_1^\star,b_2^\star)$
\end{tabular*}

\medskip

La matrice ($DV$) des $b_i^\star$ définit un parallélotope rectangle
ayant le même volume $\covol(L)$ que celui défini par les $b_i$.

\medskip

Les $b_i^\star$ n'appartiennent pas à $L$ en général.

\end{frame}
%
\begin{frame}
\frametitle{Minima successifs d'un réseau}

Soit $L$ un réseau euclidien de rang $n$ dans $\mathbb{R}^m$.  On
définit, pour $1\leq i\leq n$ :
\[
\lambda_i(L) = \min\{r\in\mathbb{R}_+ : \dim\Vect(L \cap
\mathrm{B}_{\mathrm{f}}(0,r)) \geq i\}
\]
où $\mathrm{B}_{\mathrm{f}}(0,r) = \{x\in\mathbb{R}^m :
\|x\|\leq r\}$.

\medskip

Autrement dit, $\lambda_i(L)$ est le plus petit $r$ tel qu'on
puisse trouver $i$ vecteurs $\mathbb{R}$-libres tous de
norme $\leq r$ dans $L$.

\medskip

{\footnotesize \textbf{Attention :} $L \cap
  \mathrm{B}_{\mathrm{f}}(0,\lambda_n)$ ne contient pas forcément
  une $\mathbb{Z}$-base de $L$.\par}

\bigskip

En particulier, $\lambda_1(L) = \min\{\|x\| : x\in L\setminus\{0\}\}$
est la norme du plus petit vecteur non nul de $L$.

\medskip

\textbf{Exercice :} Montrer que $\lambda_1(L) \geq \min
\{\|b^\star_i\| : 1\leq i\leq n\}$.

\smallskip

{\footnotesize \textbf{Indication :} $\|uMDV\| = \|uMD\|$ avec $MDV$
  comme dans G-S.\par}

\bigskip

\textbf{Question :} Peut-on borner $\lambda_1(L) \,\covol(L)^{-1/n}$ ?

\end{frame}
%
\begin{frame}
\frametitle{Empilements de sphères}

{\footnotesize Ici, $L$ est de rang plein.\par}\smallskip

Soit $\rho(L) := \frac{1}{2}\lambda_1(L)$.  Il s'agit du plus grand
rayon $\rho$ tel que les boules ouvertes de rayon $\rho$ centrées sur
les points de $L$ soient deux à deux disjointes.

\smallskip

La \textbf{densité} = fraction du volume occupé par les boules vaut
alors $\mathscr{V}_n \; \rho(L)^n / \covol(L)$ où\footnote{Où
  $(k+\frac{1}{2})!  := \frac{(2k+1)!!}{2^{k+1}}\sqrt{\pi}$ (et
  $(2k+1)!! = \prod \textrm{impairs}$).}  $\mathscr{V}_n :=
\frac{\pi^{n/2}}{(n/2)!}$ est le volume de la $n$-boule unité.

\smallskip

{\footnotesize Il est souvent plus commode de travailler avec
  $\rho(L)^n/\covol(L)$, ou encore
  $\lambda_1(L)\,\covol(L)^{-1/n}$.\par}

\medskip

\textbf{Question :} Quelles valeurs ces nombres peuvent-ils prendre ?
(Quel réseau empile le mieux les boules en dimension $n$ ?)  Réponse
connue pour $n\leq 8$ et $n=24$.

\medskip

\textbf{Constante de Hermite :} $\gamma_n := \sup\{\lambda_1(L)^2 :
\text{$L$ t.q. $\covol(L)=1$}\}$ {\footnotesize(atteint ; on a alors
  $\gamma_1 = 1$, $\gamma_2 = \frac{2}{3}\sqrt{3}$, $\gamma_3 =
  \sqrt[3]{2}$, $\gamma_8 = 2$, $\gamma_{24} = 4$)}.

\end{frame}
%
\begin{frame}
\frametitle{Une borne de Minkowski}

{\footnotesize Explicitons le fait que la densité d'un empilement
  est $\leq 1$.\par}

\medskip

\textbf{Théorème} (Blichfeld) : Si $L \subseteq\mathbb{R}^n$ de
rg. pl., et $S \subseteq \mathbb{R}^n$ t.q. $\vol(S) > \covol(L)$,
alors $\exists z_1\neq z_2 \in S$ t.q. $z_1-z_2 \in L$.

\smallskip

{\footnotesize \textbf{Preuve :} sinon, les $S_z :=
  (S+z)\cap\mathcal{P}$ sont disjoints (pour $z\in L$).  Or
  $\sum_z\vol(S_z) = \sum\vol(S_z-z) = \vol S > \vol\mathcal{P}$,
  contradiction.\par}

\bigskip

\textbf{Théorème} (Minkowski) : Si $L \subseteq\mathbb{R}^n$ de
rg. pl., et $S$ convexe sym\textsuperscript{que} t.q. $\vol(S) >
2^n\covol(L)$, alors $S \cap (L\setminus\{0\}) \neq \varnothing$.

\smallskip

{\footnotesize \textbf{Preuve :} $\vol(\frac{1}{2} S) = 2^{-n}\vol(S)
  > \covol(L)$ donc il existe $z_1\neq z_2 \in \frac{1}{2} S$ t.q.,
  $z_1-z_2 \in L$, or $z_1-z_2 = \frac{1}{2}(2z_1 - 2z_2) \in S$.\par}

\bigskip

\textbf{Corollaire :} $\lambda_1(L) \leq \sqrt{n}\, \covol(L)^{1/n}$
(c'est-à-dire, $\gamma_n \leq n$).

\smallskip

{\footnotesize \textbf{Preuve :} Appliquer le théorème à la boule
  ouverte de centre $0$ et rayon $\lambda_1$, et utiliser la
  minoration $\mathscr{V}_n \geq (2/\sqrt{n})^n$ (car la boule unité
  contient un cube de côté $2/\sqrt{n}$).\par}

\bigskip

\textbf{Amélioration :} $(\prod_{i=1}^n \lambda_i(L))^{1/n} \leq
\sqrt{n}\, \covol(L)^{1/n}$.

\smallskip

{\footnotesize \textbf{Idée :} Remplacer la boule par l'ellipsoïde de
  demi-axes $\lambda_1,\ldots,\lambda_n$ orientés selon le
  Gram-Schmidt des minima successifs.\par}

\end{frame}
%
\begin{frame}
\frametitle{Le réseau dual}

Si $L \subseteq \mathbb{R}^n$ est un réseau de rang plein, son
\textbf{dual} est
\[
L^* := \{y \in \mathbb{R}^n : \forall x\in L,\, x\cdot y \in \mathbb{Z}\}
\]
où $x\cdot y$ est le produit scalaire (euclidien).

\smallskip

Matriciellement, si les vecteurs sont vus comme des vecteurs-lignes :
\begin{align*}
L^* &= \{y \in \mathbb{R}^n : \forall x\in L,\, x y^{\transp} \in \mathbb{Z}\}\\
&= \{y \in \mathbb{R}^n : \forall u\in \mathbb{Z}^n,\, u B y^{\transp} \in \mathbb{Z}\}\\
&= \{y \in \mathbb{R}^n : y B^{\transp} \in \mathbb{Z}^n\}
= \mathcal{L}(B^{-\transp})
\end{align*}

C'est donc aussi un réseau, et $(L^*)^* = L$.  Covolume : $\covol(L^*)
= \covol(L)^{-1}$.  Homothéties : $(t\cdot L)^* = \frac{1}{t} \cdot
L^*$.

\smallskip

Inverse la matrice de Gram.  Cas de rang non plein : on peut définir
$\mathcal{L}(B)^* = \mathcal{L}((G^{-1} B)^{\transp}) \subseteq
\Vect_{\mathbb{R}}(\mathcal{L}(B))$.

\medskip

{\footnotesize \emph{Symétrie} sur l'espace riemannien symétrique
  $\mathit{SL}^\pm_n(\mathbb{R}) / \mathit{O}_n$.\par}

\end{frame}
%
\begin{frame}
\frametitle{Réseaux entiers}

\itempoint Si $L \subseteq L^*$, i.e., si la matrice de Gram $G$ est à
coefficients entiers, on dit que $L$ est \textbf{entier}.

\medskip

{\footnotesize Notamment, dans ce cas, le discriminant $\det G =
  \covol(L)^2$ est entier.\par}

\medskip

$\Rightarrow$ Lien avec les formes quadratiques \alert{entières}
($q(u) = \|u B\|^2 = u G u^{\transp}$).

\bigskip

\itempoint On a $L = L^*$ ssi $L$ est entier et $\covol(L) = 1$ (i.e.,
$G \in GL_n(\mathbb{Z})$).  On dit alors que $L$ est
\textbf{unimodulaire}.

\medskip

Si de plus $\|x\|^2 \in 2\mathbb{Z}$ pour tout $x \in L$ (i.e., $q$
prend des valeurs paires), on dit que $L$ est \textbf{pair} (=de
type II), sinon \textbf{impair} (=de type I).

\medskip

{\footnotesize Le plus petit rang d'un réseau unimodulaire pair
  est $8$, et ce réseau est unique à isométrie près (c'est
  $E_8$).\par}

\end{frame}
%
\begin{frame}
\frametitle{Quelques réseaux remarquables}

\itempoint $\mathbb{Z}^n$ réseau entier de covolume $1$, avec
$\lambda_1 = \cdots = \lambda_n = 1$.

\medskip

\itempoint $A_n := \{(x_0,\ldots,x_n) \in \mathbb{Z}^{n+1} :
\sum_{i=0}^{n} x_i = 0\}$ réseau entier de covolume $\sqrt{n+1}$, avec
$\lambda_1 = \cdots = \lambda_n = \sqrt{2}$.

{\footnotesize Note : $A_1$ est isométrique à $\sqrt{2}\mathbb{Z}$, et
  $A_2$ est le réseau hexagonal, $A_3$ le « cubique faces
    centrées ».\par}

\smallskip

\itempoint $A_n^* = A_n +
\mathbb{Z}(-\frac{n}{n+1},\frac{1}{n+1},\frac{1}{n+1},\ldots,\frac{1}{n+1})$
ici $\lambda_1 = \sqrt{\frac{n}{n+1}}$.

{\footnotesize Note : $A_1^*$ est isométrique à
  $\frac{1}{\sqrt{2}}\mathbb{Z}$ et $A_2^*$ à $\frac{1}{\sqrt{3}}
  A_2$, et $A_3^*$ est le « cubique centré ».\par}

\medskip

\itempoint $D_n := \{(x_1,\ldots,x_n) \in \mathbb{Z}^n : \sum_{i=1}^n
x_i \in 2\mathbb{Z}\}$ réseau entier de covolume $2$, avec $\lambda_1
= \cdots = \lambda_n = \sqrt{2}$.

{\footnotesize Note : $D_2$ est isométrique à $\sqrt{2}\mathbb{Z}^2$,
  et $D_3$ est isométrique à $A_3$.\par}

\smallskip

\itempoint $D_n^* = \mathbb{Z}^n \cup (\mathbb{Z}+\frac{1}{2})^n$,
avec $\lambda_1 = 1$ si $n\geq 4$.

{\footnotesize Note : $D_4^*$ est isométrique à $\frac{1}{\sqrt{2}}
  D_4$.\par}

\medskip

\itempoint $E_8 := \{(x_1,\ldots,x_8) \in (\mathbb{Z}^8 \cup
(\mathbb{Z}+\frac{1}{2})^8) : \sum_{i=1}^8 x_i \in 2\mathbb{Z}\}$
réseau entier de covolume $1$, avec $\lambda_1=\cdots=\lambda_8 =
\sqrt{2}$.

\end{frame}
%
\section{L'algorithme LLL}
\begin{frame}
\frametitle{Quelques problèmes algorithmiques}

{\footnotesize Algorithmiquement, on considère généralement des
  réseaux $L \subseteq \mathbb{Z}^n$ (ou en tout cas $L \subseteq
  \mathbb{Q}^n$).  Parfois $N\mathbb{Z}^n \subseteq L \subseteq
  \mathbb{Z}^n$ (« $N$-modulaires »).\par}

\medskip

\begin{beamercolorbox}[sep=.5em]{myhighlight}
\itempoint \textbf{Problème SVP$_h$} (« Shortest Vector Problem ») :
pour $h\geq 1$, donnée une base $B$ de $L = \mathcal{L}(B)$, trouver
$z\in L$ tel que $0 \neq \|z\| \leq h\cdot\lambda_1(L)$.
\end{beamercolorbox}

\smallskip

SVP$_h$ est NP-dur pour $h \lesssim \sqrt{n}$, polynomial (P) par LLL
pour $h = 2^{n/2}$.  SVP = SVP$_1$ est résoluble en
complexité $2^{O(n)}$.

\medskip

\begin{beamercolorbox}[sep=.5em]{myhighlight}
\itempoint \textbf{Problème CVP$_h$} (« Closest Vector Problem ») :
pour $h\geq 1$, donnée une base $B$ de $L = \mathcal{L}(B)$ et $t \in
\mathbb{R}^n$, trouver $z\in L$ tel que $\|t-z\| \leq
h\cdot\dist(t,L)$.
\end{beamercolorbox}

\smallskip

CVP$_h$ est au moins aussi dur que SVP$_h$, et polynomial (P) pour $h
= 2^{n/2}$ par LLL+Babai.

\end{frame}
%
\begin{frame}
\frametitle{Bases LLL-réduites}

{\footnotesize Gram-Schmidt : $b^\star_i := b_i - \sum_{j<i}
  \mu_{i,j}\, b^\star_j$ où $\mu_{i,j} := (b_i \cdot
  b^\star_j)/\|b^\star_j\|^2$.\par}

\begin{beamercolorbox}[sep=.5em]{myhighlight}
La base $b_1,\ldots,b_n$ est dite LLL-$\delta$-réduite
($\frac{1}{4}<\delta<1$) si :
\begin{itemize}
\item pour tous $i>j$, on a $|\mu_{i,j}|\leq\frac{1}{2}$, et
\item pour tout $i<n$, on a $\|b_{i+1}^\star + \mu_{i+1,i}\,
  b_i^\star\|^2 \geq \delta \cdot \|b_i^\star\|^2$.
\end{itemize}
\end{beamercolorbox}

Intuitivement, la première condition assure que les $b_i$ ne sont pas
trop loin d'être orthogonaux, et la seconde, qu'on ne gagne pas trop à
échanger $b_i \leftrightarrow b_{i+1}$ avant d'appliquer G-S.

\medskip

Notion de « bonne » base : on va voir que tout réseau a une base
LLL-réduite, calculable en temps polynomial.

\bigskip

On déduit $\|b_{i+1}^\star\|^2 \geq (\delta - \mu_{i+1,i}^2)
\|b_i^\star\|^2 \geq (\delta - \frac{1}{4}) \|b_i^\star\|^2$.

Donc $\|b_i^\star\| \geq (\delta-\frac{1}{4})^{(i-1)/2} \|b_1\|$.

Comme $\lambda_1 \geq \min\|b_i^\star\|$, on a $\|b_1\| \leq
(\delta-\frac{1}{4})^{-(n-1)/2} \lambda_1$.

\end{frame}
%
\begin{frame}
\frametitle{Opérations élémentaires}

\itempoint \textbf{Réduction} de la ligne $b_i$ par $b_j$
{\footnotesize($j<i$)} : remplacer $b_i$ par $b_i - c b_j$ (soit $B
\leftarrow (1_n - c E_{ij})B$) où $c = \lceil\mu_{i,j}\rfloor$
(arrondi\footnote{Soit $\lceil\xi\rfloor :=
  \lfloor(\xi+\frac{1}{2})\rfloor$ où $\lfloor\cdot\rfloor$ = partie
  entière.}).

\smallskip

Effet sur G-S : $\mu_{i,k} \leftarrow \mu_{i,k} - c\mu_{j,k}$, donc
$\mu_{i,j} \leftarrow |\cdot|\leq\frac{1}{2}$.\\Les $b_i^\star$ ne
changent pas.

\medskip

\itempoint \textbf{Réduction de taille} de la base :\\
\textbf{pour} $i$ allant de $2$ à $n$,\\
\leavevmode\hphantom{\textbf{pour} }\textbf{pour} $j$ allant de $i-1$ à $1$
(décroissant),\\
\leavevmode\hphantom{\textbf{pour} \textbf{pour} }\textbf{réduire}
$b_i$ par $b_j$ (soit $b_i \leftarrow b_i - \lceil\mu_{i,j}\rfloor\, b_j$).

\smallskip

Assure la propriété $|\mu_{i,j}| \leq \frac{1}{2}$.

\bigskip

\itempoint \textbf{Échange} $b_i \leftrightarrow b_{i+1}$ [et
  recalculer / m.à.j. G-S !]

\smallskip

L'échange servira à assurer la propriété de Lovász $\|b_{i+1}^\star +
\mu_{i+1,i}\, b_i^\star\|^2 \geq \delta \cdot \|b_i^\star\|^2$.

\smallskip

Il faut refaire une réduction de taille après chaque échange !

\end{frame}
%
\begin{frame}
\frametitle{L'algorithme LLL}

{\footnotesize Soit $\frac{1}{4}<\delta<1$ (typiquement $\delta =
  \frac{3}{4}$ ou mieux $\frac{1}{4} + (\frac{3}{4})^{n/(n-1)}$).\par}

\smallskip

\textbf{Algorithme de Lenstra-Lenstra-Lovász} \alert{donnés}
$b_1,\ldots,b_n$ base d'un réseau $L$ de $\mathbb{R}^m$,
\alert{calcule} une base LLL-$\delta$-réduite.

\medskip

\itempoint (1) Calculer (ou m.à.j.) Gram-Schmidt.

\itempoint (2) Réduction de taille de la base :\\
\textbf{pour} $i$ allant de $2$ à $n$,\\
\leavevmode\hphantom{\textbf{pour} }\textbf{pour} $j$ allant de $i-1$ à $1$
(décroissant),\\
\leavevmode\hphantom{\textbf{pour} \textbf{pour} }\textbf{réduire}
$b_i$ par $b_j$ (soit $b_i \leftarrow b_i - \lceil\mu_{i,j}\rfloor\, b_j$)\\
\leavevmode\hphantom{\textbf{pour} \textbf{pour} \textbf{réduire} }
(et $\mu_{i,k} \leftarrow \mu_{i,k} - \lceil\mu_{i,j}\rfloor\, \mu_{j,k}$).

\itempoint (3) S'il existe $i$ tel que $\|b_{i+1}^\star +
\mu_{i+1,i}\, b_i^\star\|^2 < \delta \cdot \|b_i^\star\|^2$ :\\
\hskip2em échanger $b_i \leftrightarrow b_{i+1}$, et retourner en (1).

\bigskip

\textbf{Théorème :} LLL termine en temps polynomial.

\smallskip

{\footnotesize\textbf{Idée :} $\prod_{i=1}^n \|b_i^\star\|^{2(n-i+1)}
  = \prod_{i=1}^n \covol(\mathcal{L}(b_1,\ldots,b_i))^2$ décroît d'un
  facteur $\delta$ pour chaque échange.\par}

\medskip

\textbf{Note :} pour $n=2$, LLL $\cong$ algo. de Lagrange|Gauß
$\approx$ « Euclide centré ».

\end{frame}
%
\begin{frame}
\frametitle{Propriétés des bases LLL-réduites}

Soit $\alpha = \frac{1}{\delta-\frac{1}{4}}$ et $b_1,\ldots,b_n$ une
base LLL-$\delta$-réduite.

\medskip

On a vu $\|b_1\| \leq \alpha^{(n-1)/2}\, \lambda_1$, donc pour
$\delta=\frac{3}{4}$ on a $\|b_1\| \leq 2^{(n-1)/2}\, \lambda_1$ et
LLL résout SVP$|_h$ pour $h = 2^{(n-1)/2}$ (renvoyer $b_1$) en temps
poly.

\medskip

Plus généralement, on a :
\begin{itemize}
\item $\|b_i\| \leq \alpha^{(n-1)/2}\, \lambda_i$
\item $\|b_1\| \leq \alpha^{(n-1)/4}\, \covol(L)^{1/n}$
\item $\prod_{i=1}^n \|b_i\| \leq \alpha^{n(n-1)/4}\, \covol(L)$
\end{itemize}

\bigskip

\emph{Expérimentalement}, sur des réseaux et bases aléatoires, on
observe des inégalités meilleures (mais toujours exponentielles), par
exemple $\|b_1\| \leq 1.022^{n}\, \covol(L)^{1/n}$.

\end{frame}
%
\begin{frame}
\frametitle{Algorithme de Babai}

Soit $L = \mathcal{L}(B)$ un réseau et $t \in \mathbb{R}^n$.  On veut
résoudre le problème CVP$_h$ avec $h = 2^{n/2}$, i.e., trouver $z\in
L$ tel que $\|z-t\| \leq 2^{n/2}\, \dist(t,L)$.
\begin{itemize}
\item Appliquer LLL avec $\delta=\frac{3}{4}$ à $B$.
\item Faire $x \leftarrow t$, puis\\
\textbf{pour} $j$ allant de $n$ à $1$ (décroissant),\\
\leavevmode\hphantom{\textbf{pour} }remplacer $x \leftarrow x - c b_j$\\
\leavevmode\hphantom{\textbf{pour} remp}où $c = \lceil(b\cdot b_j^\star)/\|b_j^\star\|^2\rfloor$.
\item Retourner $z = t-x$.
\end{itemize}

\bigskip

De façon équivalente : on choisit d'abord $c \in \mathbb{Z}$ tel que
l'hyperplan affine $cb_n^\star + \Vect(b_1,\ldots,b_{n-1})$ soit aussi
proche que possible de $t$, puis on applique récursivement pour
trouver un élément proche de $x$ dans $cb_n +
\mathcal{L}(b_1,\ldots,b_{n-1})$ (i.e., proche de $x-cb_n$ dans
$\mathcal{L}(b_1,\ldots,b_{n-1})$).

\end{frame}
%
\begin{frame}
\frametitle{Approximation diophantienne simultanée}

\itempoint Soient $(\xi_1,\ldots,\xi_r) \in \mathbb{R}$ irrationnels.
On cherche à approcher les $\xi_i$ par des rationnels $p_i/q$ \emph{de
  même dénominateur}, i.e., trouver $(p_1,\ldots,p_r) \in
\mathbb{Z}^r$ et $q \in \mathbb{N}_{>0}$ tels que les $|q \xi_i -
p_i|$ soient petits et $q$ pas trop grand.  Qualité prédite par :

\smallskip

\itempoint \textbf{Dirichlet :} Il existe des $q$ arbitrairement
grands tels que $|q\xi_i - p_i| \leq q^{-1/r}$ où $p_i = \lceil
q\xi_i\rfloor$.

\smallskip

{\footnotesize\textbf{Preuve :} Découper $(\mathbb{R}/\mathbb{Z})^r$
  en $N^r$ cubes de côté $1/N$, et considérer les $N^r+1$ classes des
  points $q\vec\xi$ pour $0\leq q\leq N^r$ : il existe $0\leq q_1 <
  q_2 \leq N^r$ tels que les classes tombent dans la même boîte, et si
  $q = q_2-q_1$ alors on a $|q\xi_i - p_i| \leq \frac{1}{N} \leq
  q^{-1/r}$.\par}

\medskip

\itempoint \textbf{Réseau :} pour $N>0$ réel, considérer l'image de
$\mathbb{Z}^{r+1} \to \mathbb{R}^{r+1}$ envoyant $(p_1,\ldots,p_r,q)$
sur $(N(q\xi_1-p_1), \penalty0 \ldots, \penalty0
N(q\xi_r-p_r),q/N^r)$.  On vient de voir que ce réseau a des petits
vecteurs non nuls.

\itempoint LLL donne $|q\xi_i-p_i| \leq 2^{r/2}/N$ avec $q \leq
2^{r/2} N^r$.

\end{frame}
%
\begin{frame}
\frametitle{Le problème du sac à dos}

\textbf{Problème :} Donnés $a_1,\ldots,a_r,s$ entiers $>0$, on cherche
un sous-ensemble $P$ de $\{1,\ldots,r\}$ tel que $\sum_{i\in P} a_i =
s$ (supposé exister).

\medskip

Approche par LLL : soit $B$ une constante bien choisie ($\lceil\sqrt{n
  2^{n}}\rceil$).  considérer l'image de $\mathbb{Z}^{r+1} \to
\mathbb{R}^{r+1}$ envoyant $(u_1,\ldots,u_r,v)$ sur $(u_1,\ldots,u_r,
B\cdot(v s - \sum u_i a_i))$.

\smallskip

Avec les bonnes conditions sur les $a_i$ (uniformément choisis sur un
intervalle assez grand) et $s$ (supérieur à $\frac{1}{2}\sum a_i$, ce
qu'on peut toujours supposer), on montre qu'avec une probabilité
extrêmement élevée, le plus court vecteur trouvé par LLL résout le
problème du sac à dos.

\end{frame}
%
\section{Réseaux et cryptographie}
\begin{frame}
\frametitle{Réseaux en cryptographie : principes}

Utilisation pour le chiffrement à clé publique :

\smallskip

\itempoint La clé secrète sera typiquement une « bonne » base d'un
réseau $L$ (ou de son dual).

\bigskip

\itempoint La clé publique sera typiquement une « mauvaise » base du
même réseau $L$.

\medskip

Il est facile de générer la mauvaise base à partir de la bonne,
difficile de faire l'opération inverse.

\bigskip

\itempoint Le chiffrement consiste à fabriquer un problème difficile à
partir d'une mauvaise base, que la connaissance d'une bonne base
permet de résoudre.

\medskip

Par exemple : pour chiffrer, écrire le message sous forme d'un petit
vecteur $e$, choisir $z$ aléatoirement dans $L$, et renvoyer $x = z +
e$.  Déchiffrer demande de retrouver $z \in L$ proche de $x$.

\end{frame}
%
\begin{frame}
\frametitle{Réseaux en cryptographie : espoirs et limitations}

Espoirs de la cryptographie basée sur les réseaux :

\smallskip

\itempoint Résistance aux \alert{ordinateurs quantiques}.

Contrairement aux problèmes de théorie des nombres (factorisation,
pb. du log discret) utilisés comme source de difficulté en
cryptographie à clé publique traditionnelle, et qui sont cassés par
les ordinateurs quantiques\footnote{Si un jour ils existent
  vraiment...}, les problèmes de réseaux \emph{paraissent} aussi
difficiles pour les ordinateurs quantiques que pour les ordinateurs
classiques.

\smallskip

\itempoint Outils plus puissants, p.ex., chiffrement complètement
homomorphe ($\Rightarrow$calculs sur les chiffrés).

\bigskip

Limitations :

\smallskip

\itempoint Taille de clés/chiffrés beaucoup plus grande.

\smallskip

\itempoint Encore mal compris : pas de paramètres de sécurité
standardisés.

\end{frame}
%
\begin{frame}
\frametitle{Réseaux $N$-modulaires}

{\tiny\textbf{Notation :} $\mathbb{Z}_{/\!N} :=
  \mathbb{Z}/N\mathbb{Z}$\par}

Un réseau $L$ tel que $N\mathbb{Z}^m \subseteq L \subseteq
\mathbb{Z}^m$ est dit \textbf{$N$-modulaire}.

Équivalent à la donnée d'un sous-groupe $L/N\mathbb{Z}^m \subseteq
\mathbb{Z}_{/\!N}^{\,m}$

(si $N{=}q$ premier, d'un sous-$\mathbb{F}_q$-esp. vect.  de
$\mathbb{F}_q^m$).

\smallskip

{\footnotesize\textbf{Attention :} Le rang du réseau ici est $m$, même
  si $L/N\mathbb{Z}^m$ est très petit.\par}

\medskip

Si $A \in (\mathbb{Z}_{/\!N})^{n\times m}$ (typiquement, $n \leq m
\approx n\log n$), soient :
\begin{beamercolorbox}[sep=.5em]{myhighlight}
\abovedisplayskip=0pt\belowdisplayskip=0pt
\[
\begin{array}{c}
\Lambda(A) :=\!\mathcal{L}(A) + N\mathbb{Z}^m = \{x\in \mathbb{Z}^m :
\exists u\in\mathbb{Z}^n,\, x \equiv u A\;[N]\}\\
\Lambda^\perp(A) :=
\{v\in\mathbb{Z}^m : A v^{\transp} \equiv 0\;[N]\}
\end{array}
\]
\end{beamercolorbox}
les réseaux $N$-modulaires (de rang $m$) engendré par les lignes de
$A$, resp. orthogonal aux lignes de $A$.

\medskip

\itempoint On a $\Lambda^\perp(A) = N \cdot \Lambda(A)^*$ et
$\Lambda(A) = N \cdot \Lambda^\perp(A)^*$.

\medskip

{\footnotesize \itempoint Si $N{=}q$ premier, et $A$ de rang $n$, on a
  $\Lambda^\perp(A) = \Lambda(B)$ où $B \in
  \mathbb{Z}_{/\!q}^{(m-n)\times m}$ de rang $m-n$ (lignes de $B$ base
  du suppl. ortho. des lignes de $A$, soit $B A^{\transp} = 0$).\par}

\smallskip

{\footnotesize \itempoint Avec haute probabilité, $\covol(\Lambda(A))
  = q^{m-n}$ et $\covol(\Lambda^\perp(A)) = q^n$.\par}

\end{frame}
%
\begin{frame}
\frametitle{« Learning With Errors » (LWE)}

{\footnotesize Soit $q$ premier.  Typiquement, $10^3 < q < 10^5$
  ici, $10^2 < n < 10^3$ et $10^3 < m < 10^4$.\par}

\medskip

Soit $A \in \mathbb{Z}_{/\!q}^{n\times m}$ tiré au hasard
uniformément.  Le vecteur $x \in \mathbb{Z}_{/\!q}^m$ est défini par
\alert{l'un des deux} procédés suivants :
\begin{itemize}
\item tiré au hasard uniformément dans $\mathbb{Z}_{/\!q}^m$, ou bien
\item calculé par $x = uA + e$ où $u \in \mathbb{Z}_{/\!q}^n$ est
  tiré au hasard uniformément, et $e \in \mathbb{Z}_{/\!q}^m$ selon
  une distribution gaussienne (arrondie aux entiers et réduite
  mod $q$).
\end{itemize}
\textbf{Défi :} distinguer ces deux cas avec probabilité $>
\frac{1}{2} + \varepsilon$.

\medskip

Si l'écart-type est assez petit, application du CVP à $x$ pour le
réseau $\Lambda(A)$.  Correction de l'« erreur » $e$.

\bigskip

\textbf{Théorème} (informel\textsuperscript{t}) : pour un écart-type
assez élevé dans la gaussienne ($>\sqrt{\frac{2\pi}{n}}$), LWE est au
moins aussi difficile que certains problèmes difficiles « standards »
sur les réseaux.

\end{frame}
%
\begin{frame}
\frametitle{Un chiffrement basé sur LWE (Regev / GPV)}

\itempoint Paramètre : $A \in \mathbb{Z}_{/\!q}^{n\times m}$ tiré au
hasard uniformément.  Clé secrète : $s \in \mathbb{Z}_{/\!q}^m$ selon
une distribution gaussienne (« petit vecteur » secret).  Clé
publique : $p := As^{\transp} \in \mathbb{Z}_{/\!q}^n$.

\medskip

\itempoint Chiffrement d'un bit $b \in \{0,1\}$ : tirer $u \in
\mathbb{Z}_{/\!q}^n$ uniformément et $(e, e_0) \in
\mathbb{Z}_{/\!q}^{m+1}$ selon une distribution gaussienne
(« erreur »).  Renvoyer $x = uA + e \in \mathbb{Z}_{/\!q}^m$ ainsi que
$c = b\lfloor\frac{q}{2}\rfloor + u \cdot p + e_0 \in
\mathbb{Z}_{/\!q}$.

\medskip

\itempoint Déchiffrement : recevant $x \in \mathbb{Z}_{/\!q}^m$ et $c
\in \mathbb{Z}_{/\!q}$, calculer $c - x \cdot s^{\transp}$, qui vaut
$b\lfloor\frac{q}{2}\rfloor + e_0 - e\cdot s^{\transp}$ : si ce nombre
est plus proche de $\frac{q}{2}$, décoder $1$, sinon, décoder $0$.
Validité : $e_0 - e\cdot s^{\transp}$ a une probabilité négligeable
d'être $\gtrsim\frac{q}{2}$.

\bigskip

{\footnotesize Le paramétrage de $m,n,q$ et les écarts-types des
  gaussiennes doit être fait pour rendre le chiffrement difficile à
  casser et la probabilité d'erreur au décodage négligeable.\par}

\end{frame}
%
\begin{frame}
\frametitle{Un chiffrement basé sur LWE : explications}

{\color{brown}\footnotesize\itempoint Paramètre : $A \in
  \mathbb{Z}_{/\!q}^{n\times m}$.  Clé secrète : $s \in
  \mathbb{Z}_{/\!q}^m$ (« petit vecteur »).  Clé publique : $p :=
  As^{\transp} \in \mathbb{Z}_{/\!q}^n$.\par}

La clé publique est plutôt $(A|p) \in
\mathbb{Z}_{/\!q}^{n\times(m+1)}$.  Soit $L := \Lambda(A|p)$ le réseau
engendré par ses lignes.

\medskip

{\color{brown}\footnotesize\itempoint Chiffrement : $x = uA + e \in
  \mathbb{Z}_{/\!q}^m$ et $c = b\lfloor\frac{q}{2}\rfloor + u \cdot p
  + e_0 \in \mathbb{Z}_{/\!q}$ où $u \in \mathbb{Z}_{/\!q}^n$ uniforme
  et $(e, e_0) \in \mathbb{Z}_{/\!q}^{m+1}$ « erreur ».\par}

On a donc $(x|p) = u (A|p) + (e|e_0) + (0|b\lfloor\frac{q}{2}\rfloor)
\in \mathbb{Z}_{/\!q}^{m+1}$ qui est soit proche de $L$, soit de $L +
(0|\lfloor\frac{q}{2}\rfloor)$.

\medskip

\itempoint La distinction entre ces deux cas est rendue possible par
la connaissance du petit vecteur $(-s|1) \in \Lambda^\perp(A|p)$ (car
on a $(A|p)(-s|1)^{\transp} = -As^{\transp} + p = 0$).

\bigskip

\textbf{Moralité :} Connaître un petit vecteur dans le réseau dual
$L^*$ permet de séparer nettement $L$ en hyperplans.

\end{frame}
%
\begin{frame}
\frametitle{Preuve de sécurité (idée)}

Preuve en deux points :

\itempoint Savoir distinguer une clé publique $p \in
\mathbb{Z}_{/\!q}^n$ (avec $p = As^{\transp}$ où $s \in
\mathbb{Z}_{/\!q}^m$ petit vecteur) d'une clé aléatoire uniforme $\in
\mathbb{Z}_{/\!q}^{n\times(m+1)}$ revient à savoir résoudre LWE.

\smallskip

{\footnotesize En effet, se donner $p = As^{\transp}$ revient à se
  donner $s$ modulo $\Lambda^\perp(A)$, c'est-à-dire un tirage $v B +
  s$ avec $v$ uniforme, où $B \in \mathbb{Z}_{/\!q}^{(m-n)\times n}$
  définit $\Lambda(B) = \Lambda^\perp(A)$.  C'est bien un
  problème LWE.\par}

\bigskip

\itempoint Savoir déchiffrer pour une clé $A' \in
\mathbb{Z}_{/\!q}^{n\times(m+1)}$ aléatoire uniforme revient à savoir
résoudre LWE.

\smallskip

{\footnotesize En effet, il s'agit de distinguer $uA' + e'$ (avec $u$
  uniforme).\par}

\end{frame}
%
\end{document}