rfe.tex

\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
 
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
 
\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


\begin{definition} Information Theoretic Fuzzy Extractor \\
An $(\mathcal{M}, m, l, t, \epsilon)$-fuzzy extractor is a pair of randomized functions $(Gen, Rep)$ such that for any $\omega,\omega' \in \mathcal{M}$:
\begin{itemize}
    \item $Gen(\omega) \rightarrow (R, P)$, with $R \in \{0,1\}^l$ a secret key and $P \in \{0,1\}^*$ a public string.
    \item $Rep(\omega', P) \overset{\mathrm{def}}{=} R'$ with $R' = R$ when $d(\omega,\omega') \leq t$.
\end{itemize}
An FE is secure if, for any arbitrary distinguisher $D$ and for any random variable $W \in \mathcal{M}$ such that $H_{\infty}(W) \geq m$ and $(R,P) \leftarrow Gen(W)$, we have:
$$| \Pr(D[R,P] = 1) - \Pr(D[U_l,P] = 1) | \leq \epsilon$$

\textbf{\textit{Reusability (IND-Fuz-CPA)}} \\
Let $\mathcal{O}$ be the oracle and $D$ be a PPT distinguisher. The IND-Fuz-CPA game goes as follows:

\begin{enumerate}
	\item $\mathcal{O}$ draws $\omega \leftarrow W$
	\item $D$ chooses a perturbation $\delta_i \in \Delta$ and sends it to $\mathcal{O}$ as a public query.
	\item $\mathcal{O}$ computes $(R_i,P_i) \leftarrow Gen(\delta_i(\omega))$ and sends $P_i$ back to $D$
	\item $D$ can repeat steps 2 and 3 up to $q$ times
	\item $D$ chooses a perturbation $\delta_j \in \Delta$ and sends it to $\mathcal{O}$ as a private query.
	\item $\mathcal{O}$ computes $(R_j,P_j) \leftarrow Gen(\delta_j(\omega))$ and sends $R_j$ back to $D$
	\item $D$ can repeat steps 5 and 6 up to $q'$ times
	\item $D$ chooses $P' \in \{P_0,\cdots,P_q\}$ the public strings resulting of public queries and sends it to $\mathcal{O}$
	\item $\mathcal{O}$ draws $b \leftarrow \{0,1\}$
	\item if $b = 1$, $\mathcal{O}$ computes $R' \leftarrow Rep(\omega,P)$, otherwise, $\mathcal{O}$ computes $R' \xleftarrow{\$} \{0,1\}^l$ and sends $R'$ to $D$
	\item $D$ can make more public or private queries, up to the respective limits, $q$ and $q'$.
	\item $D$ outputs $b' \in \{0,1\}$ and wins if $b' = b$.
\end{enumerate}


An information theoretic FE is $(\tau,q,q',\bar{t},\alpha)$-IND-Fuz-CPA secure for a family of perturbations $\Delta$ if, for any distinguisher $D$ running in time $\tau$ and making $q$ public and $q'$ private queries, with the condition on private queries that $\forall \delta \in \Delta$, $min_{\omega \in \mathcal{M}} [\omega,\delta(\omega)] > \bar{t}$, we have:
$$| \Pr(D[U_l] = 1) - \Pr(D[Rep(\delta(\omega),P)] = 1) | \leq \alpha$$
\end{definition}





\begin{definition} Computational Fuzzy Extractor \\
An $(\mathcal{M}, \mathcal{W}, l, t, \gamma)$-fuzzy extractor is a pair of randomized functions $(Gen, Rep)$ such that for any $\omega,\omega' \in \mathcal{M}$:
\begin{itemize}
    \item $Gen(\omega) \rightarrow (R, P)$, with $R \in \{0,1\}^l$ a secret key and $P \in \{0,1\}^*$ a public string.
    \item $Rep(\omega', P) \overset{\mathrm{def}}{=} R'$ with $Pr(R' = R) \geq 1 - \gamma$ when $d(\omega,\omega') \leq t$
\end{itemize}

A computational FE is $(\epsilon, s)$-hard if, for any distinguisher $D$ of size at most $s$ and for any random variable $W \in \mathcal{W}$ such that $(R,P) \leftarrow Gen(W)$, we have:
$$| \Pr(D[R,P] = 1) - \Pr(D[U_l,P] = 1) | \leq \epsilon $$

\textbf{\textit{Reusability}}
A computational FE is $(\epsilon, s, \rho)$-reusable if, for any distinguisher $D$ of size at most $s$, given arbitrary correlated random variables $W_1,\cdots,W_{\rho} \in \mathcal{W}$ such that $(R_i,P_i) \leftarrow Gen(W_i)$ for all $1 \leq i \leq \rho$, we have:
$$ | \Pr(D[R_1,\cdots,R_{\rho},P_1,\cdots,P_{\rho}] = 1) - \Pr(D[R_1,\cdots,R_{i-1},U_l,R_{i+1},\cdots,R_{\rho},P_1,\cdots,P_{\rho}] = 1) | \leq \epsilon $$
\end{definition}

\end{document}