semantic_secu_ct_ind_reduction.tex

\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts,xcolor}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newcommand{\comment}[1]{\textcolor{blue}{[#1]}}

\newenvironment{problem}[2][Problem]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
%If you want to title your bold things something different just make another thing exactly like this but replace "problem" with the name of the thing you want, like theorem or lemma or whatever
 
\begin{document}
 
%\renewcommand{\qedsymbol}{\filledbox}
%Good resources for looking up how to do stuff:
%Binary operators: http://www.access2science.com/latex/Binary.html
%General help: http://en.wikibooks.org/wiki/LaTeX/Mathematics
%Or just google stuff
 
\title{\textbf{Reusable Fuzzy Extractors}}
\author{Chloe Cachet}
%\maketitle


Let $\mathcal{M}$ be the set of all possible plaintexts, $\mathcal{C}$ be the set of all possible ciphertexts and $\mathcal{K} = \{0,1\}^n$ be the set of all possible secret keys. Define $\Pi = (Gen, Enc, Dec)$ an encryption scheme with security parameter $n$, such that $\forall k \in \mathcal{K}$, $\forall m \in \mathcal{M}$, $\forall c \in \mathcal{C}$:
\begin{itemize}
	\item $Gen$ draws a key uniformly at random from $\mathcal{K}$, $k \leftarrow Gen$ \\
	\item $c \leftarrow Enc(k,m)$ \\
	\item $Dec(k,c) = m$ when $c \leftarrow Enc(k,m)$ 
\end{itemize} 


\begin{definition} Semantic Security \\
$\Pi$ is semantically secure if, $\forall f$, $\forall m \in \mathcal{M}$, $\forall \textit{ PPT adversary } \mathcal{A}$, $\exists \textit{ PPT simulator } S$ such that:

$$ | \Pr_{k,Enc,m}[\mathcal{A}(|m|, Enc(k,m)) = f(m)] - \Pr[S(|m|) = f(m)] | \leq \epsilon $$

\comment{I'm not sure I got everything right about simulation proofs ...}

The simulation goes as follows:
\begin{enumerate}
	\item $S$ draws a key $k \leftarrow Gen$ and a random string of size $|m|$, $m' \leftarrow \{0,1\}^{|m|}$.
	\item $S$ computes $c \leftarrow Enc(k,m')$ and sends $c$ to $\mathcal{A}$
	\item $S$ returns $\mathcal{A}$'s answer.
\end{enumerate}

We thus have:

$$ \Pr[S(|m|) = f(m)] = \Pr[\mathcal{A}(|m|, Enc(k,m')) = f(m)] $$

\end{definition}

\begin{definition} Ciphertext Indistinguishability (EAV-security) \\

Let's consider the $PrivK^{EAV}_{\mathcal{A},\Pi}$ game. $\mathcal{O}$ is the oracle and $\mathcal{A}$ is a PPT adversary:

\begin{enumerate}
	\item $\mathcal{O}$ draws $k \leftarrow Gen$ 
	\item $\mathcal{A}$ sends its challenge messages $m_0, m_1 \in \mathcal{M}$ to $\mathcal{O}$
	\item $\mathcal{O}$ draws $b \leftarrow \{0,1\}$
	\item $\mathcal{O}$ computes $c \leftarrow Enc(k,m_b)$ and sends c to $\mathcal{A}$
	\item $\mathcal{A}$ returns $b' \in \{0,1\}$, $\mathcal{A}$ wins (i.e. $PrivK^{EAV}_{\mathcal{A},\Pi} = 1$) if $b' = b$ 
\end{enumerate}

An encryption scheme $\Pi$ is $PrivK^{EAV}_{\mathcal{A},\Pi}$-secure if we have:

$$ \Pr[PrivK^{EAV}_{\mathcal{A},\Pi} = 1] \leq \frac{1}{2} + \epsilon(n) $$

with $\epsilon$ a negligible function over the secure parameter $n$.

\end{definition}


\begin{proof} EAV-security $\Rightarrow$ Semantic Security \\

Let $f(m)$ be a function outputing the first bit of $m$. 
We fix an arbitrary PPT adversary $\mathcal{A}_{SIM}$. $\mathcal{A}_{SIM}$ takes as inputs $c = Enc(k,m)$ and $l = |m|$ and returns $f(m)$ (0 or 1). 
We define the oracle $\mathcal{O}$ and the PPT adversary $\mathcal{A}_{EAV}$, and the following game:

\begin{enumerate}
	\item $\mathcal{A}_{EAV}$ creates 2 messages $m_0,m_1$ such that $m_0 = 0^l$ and $m_1 = 1^l$ and sends them to $\mathcal{O}$
	\item $\mathcal{O}$ draws $k \leftarrow Gen$
	\item $\mathcal{O}$ draws $b \leftarrow \{0,1\}$ 
	\item $\mathcal{O}$ computes $c \leftarrow Enc(k,m_b)$ and sends $c$ to $\mathcal{A}_{EAV}$
	\item $\mathcal{A}_{EAV}$ forward $c$ and $l$ to $\mathcal{A}_{SIM}$ and returns whatever $\mathcal{A}_{SIM}$ outputs as $b'$. $\mathcal{A}_{EAV}$ wins when $b' = b$.
\end{enumerate}

We thus have:

$$ \Pr[PrivK^{EAV}_{\mathcal{A}_{EAV},\Pi} = 1] = \Pr[b = b'] = \Pr[\mathcal{A}_{SIM}(c,l) = f(m_b)] $$

From the EAV-security definition, we know that:

$$ \Pr[PrivK^{EAV}_{\mathcal{A}_{EAV},\Pi} = 1] \leq \frac{1}{2} + \epsilon(n) $$

As such, we also have:

$$ \Pr[\mathcal{A}_{SIM}(c,l) = f(m_b)] \leq \frac{1}{2} + \epsilon(n) $$

We can also calculate the probability of the simulator $S$ getting $f(m_b)$ given only $l$:

$$ \Pr[S(l) = f(m_b)] = \frac{1}{2} $$

As a result we have:

$$ | \Pr[\mathcal{A}_{SIM}(c,l) = f(m_b)] - \Pr[S(l) = f(m_b)] | \leq \epsilon(n) $$

And we can conclude that $\Pi$ is semantically secure.
\end{proof}



\begin{proof} Semantic Security $\Rightarrow$ EAV-security \\
\comment{really not sure of this one} \\
We fix an arbitrary PPT adversary $\mathcal{A}_{EAV}$. $\mathcal{A}_{EAV}$ outputs 2 messages $m_0, m_1$ and receives a ciphertext $c$, $\mathcal{A}_{EAV}$ then returns 0/1 according to the message it thinks $c$ is the encryption of. Let $f(m_b) = b$, we then define $\mathcal{A}_{SIM}$, a PPT adversary and $S$ a simulator as follows:

Real case:
\begin{enumerate}
	\item $\mathcal{A}_{EAV}$ generates $m_0,m_1$ such that $|m_0| = |m_1| = l$
	\item $\mathcal{A}_{SIM}$ forwards $m_0,m_1$ to the oracle
	\item the oracle draws $b \leftarrow \{0,1\}$ and $k \leftarrow Gen$ and computes $c \leftarrow Enc(k,m_b)$ and sends c to $\mathcal{A}_{SIM}$
	\item $\mathcal{A}_{SIM}$ forwards $c$ to $\mathcal{A}_{EAV}$ and outputs whatever $\mathcal{A}_{EAV}$ returns.
\end{enumerate}

We then have:

$$ \Pr[\mathcal{A}_{SIM}(l,c) = f(m_b)] = \Pr[\mathcal{A}_{EAV}(c) = b)] $$

Simulation case:
\comment{I think I have a problem in this one, can I have the adversaries also communicate with an oracle distinct from S ?} \\
\begin{enumerate}
	\item $\mathcal{A}_{EAV}$ generates $m_0,m_1$ such that $|m_0| = |m_1| = l$
	\item $\mathcal{A}_{SIM}$ sends $m_0,m_1$ to $S$
	\item $S$ draws $b \leftarrow \{0,1\}$ and $m' \leftarrow \{0,1\}^l$
	\item $S$ computes $c' \leftarrow Enc(k,m')$ and sends $c$ and $l$ to $\mathcal{A}_{SIM}$
	\item $\mathcal{A}_{SIM}$ forwards $c$ to $\mathcal{A}_{EAV}$ and outputs whatever $\mathcal{A}_{EAV}$ returns.
\end{enumerate}
 
In this case, we have:

$$ \Pr[S(l) = f(m_b)] = \Pr[\mathcal{A}_{SIM}(l,c') = f(m_b)] = \Pr[\mathcal{A}_{EAV}(c') = b)] = \frac{1}{2} $$ 

From the semantic security definition, we know that:

$$ | \Pr[\mathcal{A}_{SIM}(l, Enc(k,m_b)) = f(m_b)] - \Pr[S(l) = f(m_b)] | \leq \epsilon(n) $$

As such we have:

$$ \Pr[\mathcal{A}_{SIM}(l, Enc(k,m_b)) = f(m_b)] \leq \Pr[S(l) = f(m_b)] + \epsilon(n) $$

$$ \Leftrightarrow \Pr[\mathcal{A}_{SIM}(l, Enc(k,m_b)) = f(m_b)] \leq \frac{1}{2} + \epsilon(n) $$

$$ \Leftrightarrow \Pr[\mathcal{A}_{EAV}(Enc(k,m_b)) = b] \leq \frac{1}{2} + \epsilon(n) $$

This proves that $\Pi$ is EAV-secure.

\end{proof}

























\end{document}