adaptive_vs_static_adv.tex

\documentclass[10pt]{article}
 \usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage[makeroom]{cancel}
 
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
 
\newenvironment{problem}[2][Problem]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
 
\begin{document}

\title{\textbf{Reusable Fuzzy Extractors}}
\author{Chloe Cachet}
%\maketitle


Let $(Gen, Rep)$ be a fuzzy extractor, such that for all $\omega_i \in \mathcal{M}$, $(R_i,P_i) \leftarrow Gen(\omega_i)$. 
Let $\Delta$ be a family of perturbations such that for any $\delta_i \in \Delta$, $\delta_i(\omega) = \omega_i$. 

Calling $Gen$ generates a partition $Part$ which splits the set of all possible inputs, $\mathcal{M}$ into two subsets of equal size, $Part_1$ and $Part_2$.

An unbounded adversary can then compute all possible values for P, and build a tree of all the P values for each possible $\omega_i = \delta(\omega)$, with the corresponding winning probabilities.\\

Boyen proposes an adaptive adversary for the information theoretic model, with perturbations restricted to shifts.
Canetti proposes a static adversary for the computational model, with arbitrary perturbations. 
Putting aside the difference in models, can we write: 
\textbf{Boyen's adversary $\Rightarrow$ Canetti's adversary}

Note: equivalent to NOT Canetti's $\Rightarrow$ NOT Boyen's, meaning. \\

%\textbf{Question: Does an adaptive adversary have any advantage over a non-adaptive one ?} \\

In other words, does building the tree of $P_i$ values in an adaptive way, such that $P_i = Gen(\delta_i(\omega_{i-1}))$, improves the probability of the adversary winning the game over building the tree in a non-adaptive way such that $P_i = Gen(\delta_i(\omega))$.

We assume $\delta_i \in \Delta$ is a deterministic function of $P_i$ such that for an arbitrary adversary $\mathcal{A}_{Boy}$, we have $\delta_i \leftarrow \mathcal{A}_{Boy}(P_i)$.

%missing transition here!

\begin{definition} Universal Hash function \\
$h: U \rightarrow R $ is a Universal hash function if, $\forall x,y \in U, x \neq y$:

$$ \Pr[h(x) = h(y)] = \frac{1}{|R|} $$

$h$ is also pairwise independent if, $\forall x,y \in U, x \neq y$, $\forall a,b \in R$:

\begin{equation*}
\begin{split}
    \Pr[h(x) = a \wedge h(y)=b] & = \Pr[h(x) = a] \times \Pr[h(y)=b] \\
    & = \frac{1}{|R|^2} 
\end{split} 
\end{equation*}
\end{definition}

\begin{definition} XOR-Universal Hash function \\
$h: U \rightarrow R $ is a XOR-Universal hash function if, $\forall x,y \in U, x \neq y$, $\forall c \in R$:

$$ \Pr[h(x) \oplus h(y) = c] = \frac{1}{|R|}$$

\end{definition}

\begin{example}
Let $W$ be the set of points such that $\forall \omega \in W, H(\omega) = a \textit{ mod } p$. The family of perturbations $\Delta$ is the set of perturbations such that $\forall \delta \in \Delta, \delta(x) = x \oplus c$. The partition is defined as follows:

\begin{equation*}
    \begin{cases}
          Part_1 = 1 & \textit{if } H(x) \textit{ is odd} \\
          Part_0 = 0 & \textit{if } H(x) \textit{ is even.}
    \end{cases}
\end{equation*}

According to definition, we have $\delta(x) \in Part_0$ if and only if $H(\delta(x))$ is even.

$$ H(\delta(x)) = H(x \oplus c) = H(x) + H(c) $$

$c$ is fixed and is either even or odd, as such, we can write:
\begin{equation*}
    \begin{cases}
          \exists c_0, \forall x, \textit{ s.t. } x \oplus c_0 \in Part_0 \\
          \exists c_1, \forall x, \textit{ s.t. } x \oplus c_1 \in Part_1 
    \end{cases}
\end{equation*}

we then have the following probabilities:

\begin{equation*}
    \begin{cases}
          Pr[x \oplus c_0 \in Part_0] = 1 \textit{ and } Pr[x \oplus c_0 \in Part_1] = 0 \\
          Pr[x \oplus c_1 \in Part_1] = 1 \textit{ and } Pr[x \oplus c_1 \in Part_0] = 0 \\
    \end{cases}
\end{equation*}

\end{example}

Basing ourselves on this example, we ask the following question:

Given a partition with $|Part_0| = |Part_1|$, can we find a distribution such that 

\begin{equation*}
    \begin{cases}
          \forall c, \forall x, Pr[x \oplus c \in Part_0] \ngtr \frac{1}{2} \\
          \forall c, \forall x, Pr[x \oplus c \in Part_1] \ngtr \frac{1}{2}
    \end{cases}
\end{equation*}

in other words, we want to find a distribution for which we cannot find $c_0, c_1$ such that :

\begin{equation*}
    \begin{cases}
          \exists c_0, \forall x, \textit{ s.t. } x \oplus c_0 \in Part_0 \\
          \exists c_1, \forall x, \textit{ s.t. } x \oplus c_1 \in Part_1 
    \end{cases}
\end{equation*}

We consider an arbitrary distribution $B_{l,x}$ as a Hamming ball centered on $x$ and of radius $l$, such that:

$$ B_{l,x} = \sum_{i=0}^l \binom{n}{i} (q-1)^i = \sum_{i=0}^l \frac{n!}{i!(n-i)!} (q-1)^i \approx \binom{n}{l}(q-1)^l $$ 

with $q \geq 2$ and $n \geq r \geq 1$. %We then give an approximation of $\binom{n}{i}$, $\forall 1 \leq i \leq n $:

%$$ (\frac{n}{i})^i \leq \binom{n}{i} \leq 2^n $$ 

Let $\Delta$ be a shift such that $\Delta(x) = x + 1$, $\Delta$ then takes inputs in $B_{l,x}$ and its outputs are in $B_{l,x+1}$.

We then have:

$$ B_{l,x} \cap B_{l,x+1} \geq B_{l-1,x} $$

and 

%\begin{equation*}
%\begin{split}
%    \frac{B_{l-1,x}}{B_{l,x}} & = \frac{\sum_{i=0}^{l-1} \binom{n}{i} (q-1)^i}{\sum_{i=0}^l \binom{n}{i} (q-1)^i} \\
%    & \leq \frac{\sum_{i=0}^{l-1} 2^n (q-1)^i}{\sum_{i=0}^l 2^n (q-1)^i} \\
%\end{split}
%\end{equation*}

\begin{equation*}
\begin{split}
    \frac{B_{l-1,x}}{B_{l,x}} & = \frac{\sum_{i=0}^{l-1} \binom{n}{i} (q-1)^i}{\sum_{i=0}^l \binom{n}{i} (q-1)^i} \\
    & \approx \frac{\binom{n}{l-1}(q-1)^{l-1}}{\binom{n}{l}(q-1)^l} \\
    & \approx \frac{1}{(q-1)} \times \frac{\cancel{n!}}{(l-1)!(n-(l-1))!} \times \frac{l!(n-l)!}{\cancel{n!}} \\
    & \approx \frac{1}{(q-1)} \times \frac{l\cancel{(l-1)!}\cancel{(n-l)!}}{\cancel{(l-1)!}(n-l+1)\cancel{(n-l)!}} \\
    & \approx \frac{l}{(q-1) \times (n-l+1)} \\
\end{split} 
\end{equation*}



















\end{document}