Skip to content
Snippets Groups Projects
Select Git revision
  • 76655f4b8b0daa055c6091cd576e77601bb5e6f4
  • main default protected
  • vac_in_initial_conditions
3 results

kondo.py

Blame
  • 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}