Select Git revision
motivation.tex
motivation.tex 5.44 KiB
\section{Motivation}
\begin{frame}[allowframebreaks]
\frametitle{Where are we?}
\begin{block}{Hard Homogeneous Spaces (Couveignes \cite{DBLP:journals/iacr/Couveignes06})}
A hard homogeneous space \(\left(\mathcal E,\mathcal G\right)\) is
\begin{itemize}
\item a set \(\mathcal E\),
\item a group \(\left(\mathcal G,\odot\right)\) and
\item an action \(\ast: \mathcal G\times \mathcal E \to \mathcal E\)
\end{itemize}
\end{block}
%\pause
\begin{block}{Properties of \(\ast\)}
\begin{itemize}
\item Compatibility: \(\forall g,g' \in \mathcal G ~\forall E \in \mathcal E \colon g \ast \left(g'\ast E\right) = \left(g\odot g'\right) E\)
\item Identity: \(\forall E \in \mathcal E \colon i \ast E = E \Leftrightarrow i\) is the neutral element in \(\mathcal G\)
\item Transitivity: \(\forall E,E'\in \mathcal E ~\exists ! g \in \mathcal G \colon g \ast E = E'\)
\end{itemize}
\end{block}
%\end{frame}
%\begin{frame}
\begin{block}{Notation}
For arbitrary \(E\in\mathcal E\), \(g\in\mathcal G\) with prime order \(p\vert \#\mathcal G\) and \(s \in \Z_p\), we denote
\[\left[s\right] E := g^s \ast E.\]
\end{block}
\begin{remark}
For \(s,s'\in \Z_p\) and \(E\in\mathcal E\), we have
\[\left[s\right] \left(\left[s'\right] E\right) = \left[s+s'\right] E.\]
\end{remark}
\begin{block}{The Group Action Inverse Problem (GAIP)}
Given two elements \(E,E' \in \mathcal E\), find \(g\in \mathcal G\) with
\[g\ast E = E'.\]
\end{block}
\end{frame}
\begin{frame}
\frametitle{Secret Sharing Schemes}
\begin{itemize}
\item Distribute a secret \(s\) among \(n\) shareholders via
\[ \mathcal S.\share\paren* s\]
\item Reconstruct a shared secret via
\[ \SH.\rec\paren*{\set{s_i}_{P_i \in S'}} \]
for an authorised set \(S'\in \Gamma\).
\end{itemize}
\begin{definition}[Superauthorised Sets]
A \highlight{superauthorised set} of shareholders is a set \(S^\ast\), so that
\[\forall P \in S^\ast \colon S^\ast \setminus\set{P} \in \Gamma.\]
\end{definition}
\end{frame}
\begin{frame}
\frametitle{Key Exchange Mechanisms}
\begin{center}
\begin{tikzpicture}
\begin{scope}[minimum size = .7cm]
\node [alice] (alice) at (-3,0){Alice};
\node [bob] (bob) at (3,0){Bob};
\end{scope}
\pause
\node [left = .5 of alice] (pair) {$\left(\sk,\pk\right)$};
%\node [above = 3 of alice] (pk) {$\pk$};
%\draw [->] (alice) -- (pk);
\pause
\node [above = 2.5 of bob] (encaps) {$\encaps \paren* \pk$};
\node [above = 0.5 of bob] (keybob) {$\key$};
\node [above = 2.5 of alice] (cipher) {$c$};
\draw [->] (encaps) -- (cipher);
\draw [->] (encaps) -- (keybob);
\pause
\node [above = 1.5 of alice] (decaps) {$\decaps\paren *{\sk,c}$};
\draw [->] (cipher) -- (decaps);
\node [above = 0.5 of alice] (keyalice) {$\key$};
\draw [->] (decaps) -- (keyalice);
\pause
\node [draw, red, inner sep = -.1em, shape = rectangle, fit=(decaps)] {};
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}
\frametitle{A Decapsulation Protocol with Shared Secret Key \cite{FeoM20}}
\begin{center}
\begin{tikzpicture}
\def\radius{2cm}
\begin{scope}[minimum size = .7cm]
\node [charlie] (sh1) at (40:\radius) {$s_1$};
\node [dave](sh2) at (140:\radius){$s_2$};
\node [maninblack] (sh3) at (220:\radius){$s_3$};
\node [physician] (sh4) at (320:\radius){$s_4$};
\end{scope}
\node (sk) at (0,0) {$\sk$};
\draw [help lines] (sk) edge (sh1) edge (sh2) edge (sh3) edge (sh4);
\pause
\node [right=of sh1] (cipher) {$E_0 = c$};
\coordinate [left = of sh2] (bla) ;
\draw [->] (cipher) -- (sh1);
\pause
\draw [->, >=Stealth, bend right] (sh1) edge node [midway, above] {$ E^1 = \left[L_{1,S'} s_1\right] E_0$} (sh2) ;
\draw [->, >=Stealth, bend right] (sh2) edge node [midway, left] {$ E^2 = \left[L_{2,S'} s_2\right] E_1$} (sh3) ;
\draw [->, >=Stealth, bend right] (sh3) edge node [midway, below] {$ E^3 = \left[L_{3,S'} s_3\right] E_2$} (sh4) ;
\node [right = of sh4] (key) {$\key = \left[L_{4,S'} s_4\right] E^3$};
\draw [->] (sh4) -- (key);
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}
\frametitle{Features of the Protocol}
\begin{block}{Advantages}
\begin{itemize}
\item Simulatable
\item Authorised set of shareholders suffices
\item Turn order is variable
\end{itemize}
\end{block}
\pause
\begin{problem}
Passive security: misbehaving shareholders cannot be detected.
\end{problem}
\end{frame}
\begin{frame}
\frametitle{A Misbehaving Shareholder}
\begin{center}
\begin{tikzpicture}
\def\radius{2cm}
\begin{scope}[minimum size = .7cm]
\node [charlie] (sh1) at (40:\radius) {$s_1$};
\node [devil](sh2) at (140:\radius){$s_2$};
\node [maninblack] (sh3) at (220:\radius){$s_3$};
\node [physician] (sh4) at (320:\radius){$s_4$};
\end{scope}
\node (sk) at (0,0) {$\sk$};
\draw [help lines] (sk) edge (sh1) edge (sh2) edge (sh3) edge (sh4);
%\pause
\node [right=of sh1] (cipher) {$E_0 = c$};
\coordinate [left = of sh2] (bla) ;
\draw [->] (cipher) -- (sh1);
%\pause
\draw [->, >=Stealth, bend right] (sh1) edge node [midway, above] {$ E^1 = \left[L_{1,S'} s_1\right] E_0$} (sh2) ;
\draw [->, >=Stealth, bend right] (sh2) edge node [midway, left, color = red] {$ {E^2} \neq \left[L_{2,S'} s_2\right] E_1$} (sh3) ;
\draw [->, >=Stealth, bend right] (sh3) edge node [midway, below] {$ E^3 = \left[L_{3,S'} s_3\right] E_2$} (sh4) ;
\node [right = of sh4] (key) {$\key = \left[L_{4,S'} s_4\right] E^3$};
\draw [->] (sh4) -- (key);
\end{tikzpicture}
\end{center}
\end{frame}