kem.tex

\section{Encapsulation Schemes}
\label{sec:kem}
 \task{2/26: revisit everything here in light of current encryption scheme syntax.} 

\paragraph{Encapsulation schemes. } 
Let $\pubkeys, \seckeys, \adata, \pubivs, \secivs$ be the sets of public keys, secret keys, associated data, public-IVs and secret-IVs (resp.), as before, and let $\keys,\wraps$ be a nonempty sets.
%
An encapsulation scheme is a triple$\encapscheme=(\pkgen,\encap,\decap)$.   The randomized \emph{key generation} algorithm~$\pkgen$ takes no input and returns a public-key, secret-key pair $(\pk,\sk)$.  We write $(\pk,\sk)\getsr\pkgen$ for the operation of key generation. \tsnote{Should $\pkgen$ take AD as input?  What have labeled KEM schemes done in the past?}

The encapsulation algorithm $\encap \colon \pubkeys \times \adata \times \pubivs \times \secivs \to \keys \times \wraps$ takes a public-key~$\pk\in\pubkeys$, associated data~$\header \in \adata$, public-IV~$\pubiv \in \pubivs$, secret-IV~$\seciv \in \secivs$, and returns a key $K \in \keys$ and an encapsulation $X \in \wraps$. 
When $\secivs$ is empty, then the encapsulation algorithm is randomized.  Otherwise, it is \emph{IV-based} and deterministic.  Following our notational conventions, we write $\encapprim{\pk}{\header,\pubiv}{\seciv}$ for the operation of encapsulation, and $\encapprimO{\pk}{\header,\pubiv}{\seciv}{\mathcal{O}}$ when it takes an oracle.  When one or more of $\header,\pubiv$, or~$\seciv$ is absent, it will be clear from context (rather than position) what inputs are present.

The decapsulation algorithm $\decap \colon \seckeys \times \adata \times \pubivs \times \wraps \to \keys \cup \{\bot\}$ takes a secret-key~$\sk\in\seckeys$, associated data~$\header \in \adata$, public-IV~$\pubiv \in \pubivs$ and an encapsulation $X \in \wraps$, and returns a key $K \in \keys$, or the distinguished symbol~$\bot \not\in \keys$.  We write $K \gets \decapprim{\sk}{\header,\pubiv}{\wrap}$ for the operation of decapsulation. 

For proper operation, we require that for all $(\pk,\sk)\in\pubkeys\times\seckeys$, $\header\in\adata$, $\pubiv\in\pubivs$, $\seciv\in\secivs$, if $\encapprim{\pk}{\header,\pubiv}{\seciv}$ returns $(K,\wrap)$, then $\decapprim{\sk}{\header,\pubiv}{\wrap}=K$.

Our formalization of encapsulation schemes is a bit non-standard, as it allows encapsulation to take IVs and associated data.

\paragraph{Security notions. } In Figure~\ref{fig:kem-notions} we give the standard security experiment for a randomized KEM scheme.  On the right, we give an experiment for an IV-based KEM scheme.  It allows multiple oracle queries to an encapsulation oracle, each using a secret-IV~$\seciv$ that was sampled by algorithm~$\advD$.  Note that adversary~$\advA$ must be nonce-respecting over public-IV values in this experiment.
As before we define corresponding advantage measures for a given adversary~$\advA$, sampler~$\advD$, and scheme $\encapscheme$ as
\begin{align*}
\AdvKEM{\encapscheme}{\advA}&=2\Prob{\ExpKEM{\encapscheme}{\advD,\advA}=1}-1\\ \AdvKEMd{\encapscheme}{\advD,\advA}&=2\Prob{\ExpKEMd{\encapscheme}{\advD,\advA}=1}-1
\end{align*}
respectively.  In both experiments, we track the time-complexity~$t$ of~$\advA$, relative to some understood model of computation.  For the IV-based KEM experiement, we additionally track (1) the query-complexity~$q$, measured as the number of queries made by~$\advA$ to its oracle; and (2) the total query-length~$\sigma$, defined the be the sum over all query lengths, where $|(\header,\pubiv)|=|\header|+|\pubiv|$.


\begin{figure}
\begin{center}
\begin{tabular}{cc}
\fpage{.25}{
\hpagess{.99}{.01}
{
 \underline{$\ExpKEM{\encapscheme}{\advA}$}:\\[2pt]
 $(\pk,\sk)\getsr\pkgen$\\
 $K_0 \getsr \keys$\\ 
 $(K_1,X) \getsr \encapprim{\pk}{}{}$\\
 $b\getsr\bits$\\ 
 $b'\getsr\advA(\pk,(K_b,X))$\\
 Return $[b'=b]$
}
{}  %%%% <--- Getting the left and right fpages to line up was a pain in the ass.  I ended up using this hack....
}
&
\fpage{.5}{
 \hpages{.45}{
  \underline{$\ExpKEMd{\encapscheme}{\advD,\advA}$}:\\[2pt]
  $(\pk,\sk)\getsr\pkgen$\\
  $\seciv \getsr \advD$\\
  $b\getsr\bits$\\ 
  $b'\getsr\advA^{\encapOracle(\cdot,\cdot)}(\pk)$\\
  Return $[b'=b]$
  }
  {
  \Oracle{$\encapOracle(\header,\pubiv)$}:\\[2pt]
  $K_0 \getsr \keys$ \\ 
  $(K_1,X) \gets \encapprim{\pk}{\header,\pubiv}{\seciv}$\\
  Return $(K_b,X)$
  }
 } 
\end{tabular}
\caption{\textbf{Left:} Security notion for randomized KEM scheme $\encapscheme$ with output key set~$\keys$.  \textbf{Right:} Security notion for IV-based KEM scheme $\encapscheme$ with output key set~$\keys$, and secret-IV sampler~$\advD$.  The adversary~$\advA$ is restricted to be nonce-respecting for the public-IV.}
\label{fig:kem-notions}
\end{center}
\end{figure}