%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[mathserif]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\DeclareUnicodeCharacter{00A0}{~}
\usepackage{CJKutf8}
% Beamer theme:
\usetheme[right]{Berkeley}
\usecolortheme{sidebartab}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{textcomp}
\usepackage{eurosym}
\DeclareUnicodeCharacter{20AC}{\euro}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{matrix,arrows,snakes}
\tikzstyle{actor}=[rectangle,fill=green!20,draw=black,line width=1pt,inner sep=.4em]
\tikzstyle{oper}=[circle,fill=blue!20,draw=black,line width=1pt,inner sep=.4em]
\tikzstyle{foo}=[rectangle,rounded corners,draw=black,line width=1pt,inner sep=.4em]
\tikzstyle{every path}=[line width=1.8pt]
\tikzstyle{every picture}=[>=stealth]
%
\newcommand{\itempoint}{\strut\hbox{\color{beamerstructure}\donotcoloroutermaths$\blacktriangleright$}\nobreak\hskip.5em plus.5em\relax}
%
\title[\rlap{Fourtytwofish}]{Perfect Localized Security\\
of the Fourtytwofish Cipher\\
in the Delphic Oracle Model}
\subtitle{La spatialisation de Poisson\\de Pharse à Trappes}
\author[David A. Madore]{David A. Madore\\TELECOM ParisTech\\
\texttt{david.madore@enst.fr}\\\texttt{http://perso.enst.fr/\char`\~madore/}}
\date{2008-W14-2}
\logo{\includegraphics[height=0.5cm]{42fish.jpg}}
\beamertemplatenavigationsymbolsempty
\usenavigationsymbolstemplate{\vbox{\hbox{\footnotesize\insertframenumber/\inserttotalframenumber}}}
%\setbeamercovered{transparent}
\setbeamercovered{invisible}
\begin{document}
%
\frame{\titlepage}
%
\section*{Outline}
\begin{frame}
\frametitle{Outline}
\tableofcontents
\end{frame}
%
\section[Fourtytwofish background]{Background on the fourtytwofish cipher}
\subsection{History}
\begin{frame}
\frametitle{History of fourtytwofish}
Belongs to a \alert{long line of ciphers} by \alert{respected cryptographers}:
\begin{itemize}
\item Blowfish (B. Schneier, 1993)
\item Twofish (B. Schneier \& al, 1998)
\item Threefish (H. Sonnenregner, 1999) --- broken 1999
\item Fourfish (H. Sonnenregner, 1999) --- broken 1999
\item Fivefish (H. Sonnenregner, 1999) --- broken 2000
\item Sixfish (H. Sonnenregner, 2000) --- broken 2000
\item ...
\item Fourtyfish (H. Sonnenregner, 2007) --- broken 2008
\item Fourtyonefish (H. Sonnenregner, 2008) --- broken 2008
\item Fourtytwofish (H. Sonnenregner, 2008)
\end{itemize}

{\footnotesize
Note: some (but \underbar{not all}) were broken.
\par}
\end{frame}
%
\subsection{Localized security}
\begin{frame}
\frametitle{What is ordinary security?}

\begin{block}{Ordinary security}
Alice uses the cipher to \alert{tell Bob a secret}

The attacker Eve (``eavesdropper'') \alert{cannot guess the secret} without
knowing the encryption key
\end{block}

\begin{center}
\smash{\rlap{\textbf{Diagram:}}}
\begin{tikzpicture}
\node[actor] (A) at (0,0) {\strut\smash{Alice}};
\node[actor] (B) at (7,0) {\strut\smash{Bob}};
\draw[->] (A) -- node[very near end,above] {\footnotesize tells secret} (B);
\node[actor] (E) at (3.5,1) {\strut\smash{Eve}};
\draw[->,densely dashed] (E) .. controls +(left:1cm) and +(up:1cm) .. (2,0);
\node[actor] (Z) at (1.5,-1) {\strut\smash{Zachary}};
\node[actor] (Y) at (5.5,-1) {\strut\smash{Yvonne}};
\draw[->,snake=snake,line after snake=0.4cm] (Y)
-- node[below] {\footnotesize cool, wavy line} (Z);
\end{tikzpicture}
\end{center}

{\footnotesize
Note: Yvonne and Zachary have fun with TikZ while Alice tells Bob her
meaningless secret.
\par}

\end{frame}
%
\begin{frame}
\frametitle{What is \emph{localized} security?}

\begin{block}{Localized security}
Now Alice \alert{does not tell Bob} the secret \underbar{at all}
\end{block}

\begin{center}
\smash{\rlap{\textbf{Diagram:}}}
\begin{tikzpicture}
\node[actor] (A) at (0,0) {\strut\smash{Alice}};
\node[actor] (B) at (7,0) {\strut\smash{Bob}};
\draw[transparent] (A) -- node[very near end,above,opaque] {\footnotesize nothing} (B);
\draw[loosely dotted] (A) -- (4,0);
\node[actor] (E) at (3.5,1) {\strut\smash{Eve}};
\draw[->,densely dashed] (E) .. controls +(left:1cm) and +(up:1cm) .. (2,0);
\end{tikzpicture}
\end{center}

\pause

\fbox{Much more \alert{difficult}: ever try to keep a
  secret for yourself?}

\end{frame}
%
\subsection[Goals]{Goals of fourtytwofish}
\begin{frame}
\frametitle{Fourtytwofish aims at \emph{perfect localized security}}

Another cool TikZ picture:

\begin{center}
\begin{tikzpicture}
\node[actor] (A) at (0,0) {\strut\smash{Alice}};
\node[actor] (B) at (7,0) {\strut\smash{Bob}};
\node[actor] (Bbar) at (7,-1) {\strut\smash{\emph{not} Bob}};
\node[oper] (cipher) at (3.5,0) {42fish};
\draw[->] (A) -- node[near start,above] {\footnotesize \ \ plaintext} (cipher)
-- node[near end,above,sloped] {\footnotesize gibberish\ \ } (Bbar);
\node[actor] (C) at (2,-2) {\strut\smash{Alice's boyfriend}};
\draw[->] (A) -- node[near end,above,sloped] {\footnotesize gossip} (C);
\node[actor,text width=2cm,text centered] (D) at (5.5,-2.5) {\tiny Alice's boyfriend's girlfriend (Eve)};
\draw[->] (C) -- (D);
\node (etc) at (7.5,-2) {...};
\draw[->] (D) -- (etc);
\draw[->] (etc) -- (Bbar);
\end{tikzpicture}
\end{center}

\end{frame}
%
\subsection{Design}
\begin{frame}
\frametitle{Fourtytwofish design}

\begin{block}{Design principles}
\begin{itemize}
\item Simple and elegant design
\item No unexplained pieces
\item Peer-reviewed on Slashdot.org
\end{itemize}
\end{block}

\begin{center}
\begin{tikzpicture}
\draw[line width=0.5pt,snake=coil,segment amplitude=6pt] (2,-2.8) -- (2,0.8);
\node[actor] (M) at (0,0) {\strut\smash{plaintext}};
\node (stock) at (4,0) {\footnotesize stock exchange};
\draw[->] (M) -- (stock.mid west);
\node (weather) at (4,-0.8) {\footnotesize weather forecast};
\draw[->] (M) -- (weather.mid west);
\node[foo,draw=red] (herring) at (7,-0.8) {\strut\smash{herring}};
\node[foo] (shark) at (7,0.8) {\strut\smash{big shark}};
\draw[>->] (herring) -- node[right]{\footnotesize eaten} (shark);
\draw[line width=1pt,double distance=2pt] (shark) -- (stock);
\node (fprint) at (6,-1.6) {\tiny annoying fine print};
\draw[->] (stock.mid east) .. controls +(-20:.5cm) and +(110:.5cm) .. (fprint.north);
\draw[->] (weather.mid east) .. controls +(east:.2cm) and +(110:.3cm) .. (fprint.north);
\node[actor] (C) at (7,-2.5) {\strut\smash{ciphertext}};
\node (nowhere) at (4,-2.5) {\footnotesize nowhere};
\draw[->] (nowhere) -- (C);
\draw[*->] (nowhere) -- (weather);
\node[circle,shading=ball,ball color=gray,minimum size=2em] (ball) at (1,-1.5) {};
\node[rotate=180] (interrobang) at (3,-1.5) {\rmfamily\huge\textinterrobang};
\draw[o->] (interrobang) -- (ball);
\node[oper] (S) at (0,-2.2) {S-box};
\draw[left hook-] (M) -- (S);
\node[actor] (magic) at (1.8,-2.5) {\strut\smash{MAGIC}};
\draw[->] (magic) -- (nowhere);
\draw (S.east) .. controls +(east:.5cm) and +(west:.5cm) .. (magic.west);
\end{tikzpicture}
\end{center}

\end{frame}
%
\section{Oracles and security}
\subsection{Oracles}
\begin{frame}
\frametitle{What is an Oracle?}

\begin{center}
\includegraphics[scale=0.5]{Oracle_logo.pdf}
\end{center}

\begin{block}{How an Oracle works}
\begin{itemize}
\item Question goes in
\item Sacrifice made to gods (or higher powers: computers...)
\item Divinely inspired answer comes out
\end{itemize}
\end{block}

\begin{center}
\begin{tikzpicture}[scale=0.5]
\node (in) at (0,0) {\footnotesize question};
\node (out) at (7,0) {\footnotesize answer};
\node[oper,text centered] (oracle) at (3.5,0) {\footnotesize oracle};
\draw[->] (in) -- (oracle) -- (out);
\end{tikzpicture}
\end{center}

Example: \begin{CJK}{UTF8}{min}易經\end{CJK} (made in China)

\end{frame}
%
\subsection{Random oracles}
\begin{frame}
\frametitle{What is a random oracle?}

\alert<1>{Cheap plastic imitation} of a real oracle,
often used in cryptography:

\begin{center}
\begin{tikzpicture}
\node (in) at (0,0) {fine question};
\node (out) at (7,0) {garbage};
\node[oper,text width=1.5cm,text centered] (oracle) at (3.5,0) {random oracle};
\draw[->] (in) -- (oracle) -- (out);
\end{tikzpicture}
\end{center}

\pause

\textbf{Example:}

--- Tell me, O Mighty Oracle, tell me the answer to my question: how
can I make out with Brad Pitt\footnote<2->{Replace with Angelina Jolie
  according to your tastes.}?

\pause

--- \texttt{5d9ba10c8d2d8d6b1b597f11d55cc435237669ae}

\smallskip

\textbf{Not very useful!}

\end{frame}
%
\subsection{The Delphic Oracle}
\begin{frame}
\frametitle{Introducing the Delphic Oracle}

\textbf{Idea:} instead of these useless random oracles, introduce the
\alert{Delphic Oracle} in cryptographic proofs.

\pause

\begin{block}{The Delphic Oracle}
\begin{itemize}
\item Established in Delphi, Greece (circa 8\textsuperscript{th} century BCE)
\item Presided by priestess of Apollo
\item Respectable reputation
\item Foretold Alexander's conquests, Nero's death,
Hadrian's rise as Emperor, etc.
\end{itemize}
\end{block}

\end{frame}
%
\begin{frame}
\frametitle{Use in cryptography}

\begin{center}
\smash{\rlap{\textbf{Model:}}}
\begin{tikzpicture}
\node (in) at (0,0) {fine question};
\node (out) at (7,0) {desired answer};
\node (bribe) at (1,-1) {\footnotesize bribe};
\node[oper,text width=1.5cm,text centered] (oracle) at (3.5,0) {Delphic Oracle};
\draw[->] (in) -- (oracle) -- (out);
\draw[->] (bribe) -- (oracle);
\end{tikzpicture}
\end{center}

\pause

\textbf{Example:}

--- Tell me, O Mighty Oracle, tell me the answer to my question: is my
cunningly devised cipher unbreakable?

\pause

--- Of course it is, Sir.  Now, do you wish to buy a stucco bust of
Socrates for only 9.99€?

\pause\smallskip

\textbf{Much more useful!} (...except for the bust of Socrates,
which is rather tacky)

\end{frame}
%
\section{The main result}
\begin{frame}
\frametitle{Statement of the main theorem}

\begin{theorem}
Fourtytwofish achieves \alert{perfect localized security} in the
Delphic Oracle model.
\end{theorem}

\pause

Some techniques used in proof:
\begin{itemize}
\item Long abstruse results from algebraic geometry.
\item Large body of numerical evidence.
\item Vigorous handwaving.
\item Personal communication / divine inspiration.
\item \underline{Zero-content} proof techniques.
\end{itemize}

\smallskip

{\footnotesize
The details are left as an exercise.
\par}

\end{frame}
%
\begin{frame}
\frametitle{The key lemma}

\textbf{Assume}
\begin{itemize}
\item $X$ is a proper locally pseudo-factorial quasi-Gorenstein
  universally catenary almost everywhere noetherian semi-effective
  excellent log-scheme with at most $\mathbb{Q}$-divisorial and
  $q$-log-canonical singularities,
\item $Y \buildrel f\over \to X$ is flat, crepant and smooth in
  codimension~$\leq 2$ with $Y$ Cohen-Macaulay,
\item $\ker[H^p(Y, f^{?}({\Omega^q_{X/Z}}^{\otimes n})) \to H^p(Y,
  f^{?}(\Omega^q_{X/Z})^{\otimes n})] = 0$ for some $n$ (for all $p$,
  for all $q$, for some $X\to Z$);
\end{itemize}
\pause
\textbf{then}
\begin{itemize}
\item the obvious conclusion follows.
\end{itemize}

\smallskip

{\footnotesize
Note in terminology: $2 := 1+1$.
\par}

\end{frame}
%
\section{Conclusion}
\begin{frame}
\frametitle{Applications}

\textbf{Expected applications:}
\begin{itemize}
\item Patents
\item Lots of money
\end{itemize}

\pause\bigskip

\textbf{Applications so far:}
\begin{itemize}
\item Talks at prestigious conferences
\item Busts of Socrates, Pericles, etc.  (made of stucco)
\end{itemize}

\end{frame}
%
\section{Bibliography}
\begin{frame}
\frametitle{References}

\begin{thebibliography}{foo}
\setbeamertemplate{bibliography item}[text]
\bibitem[refneeded]{refneeded} Anonymous (author unknown),
  \newblock\textit{Reference needed}, (cited in \cite{WP}).
\setbeamertemplate{bibliography item}[article]
\bibitem{prest} Prestigious author,
  \newblock\textit{Prestigious title having nothing to do with
    Fourtytwofish},
  \newblock Presitigious journal.
\setbeamertemplate{bibliography item}[book]
\bibitem{bible} God,
  \newblock\textit{The Bible}.
\setbeamertemplate{bibliography item}[triangle]
\bibitem{privcomm} God,
  \newblock personal communication.
\setbeamertemplate{bibliography item}[text]
\bibitem[Wikipedia]{WP} J. Wales \& al.,
  \newblock\textit{Wikipedia},
  \newblock published online.
\end{thebibliography}

\end{frame}
%
\begin{frame}
\frametitle{The End}

\huge So long, and thanks for all the fish!

\bigskip

{\footnotesize
(Any questions?)
\par}
\end{frame}
%
\end{document}
