security.tex

\section{Security}

\begin{lemma}
oblivSort leaks no information whenever the index, $A$, being sorted on
has a public distribution.
\end{lemma}

\begin{proof}
First, the array $A$ is shuffled obliviously.
($B$ is also shuffled obliviously using the same permutation.)
Since this operation is done within a secure computation,
nothing is leaked by performing this computation.
Furthermore, after this computation, $\hat{A}$ contains
no sensitive information.
The original order of the elements has been entirely masked by a
random permutation and the contents were already known.
Therefore revealing $\hat{A}$ leaks no information.
Finally, the sorting leaks no information because it is performed
based on data that has already been revealed (namely $\tilde{A}$).
\end{proof}

\begin{theorem}
SqrtORAM.shuffle does not leak any information
\end{theorem}

\begin{proof}
We have that OblivSort leaks no information if the indexes sorted on
follow a public distribution. In the case of the first call
to OblivSort on line \ref{line:first_sort}, this is true since
the array $ind$ contains exactly one occurrence of $(x, y)$ 
for all $x, y \in [\sqrt{n}]$.

The evaluation of the PRF on line \ref{line:prf_eval} is performed
within the secure computation with the output being a secret value.
Therefore nothing is learned about the input in this step.

Viewed as a function $B_k(i)$ is invertible and, since the domain and range
are equal, $B_k(i)$ is a permutation. 
Since it has every possible input, it also has every possible output.
Therefore the distribution of $B_k(i)$ is public (though its order is secret.)
Therefore, when OblivSort is evaluated on line \ref{line:second_sort} 
it leaks nothing.

Lastly initialization of a new stash (using a public parameter) leaks nothing.

Therefore, the function SqrtORAM.shuffle leaks no information.
\end{proof}

\begin{theorem}
For certain values of $c$ (though not the one used in the implementation)
the ORAM protocol is secure.
\end{theorem}

\begin{proof}
Patarin showed that a Feistel cipher with 7 rounds is a
permutation from $[n] \rightarrow [n]$ 
secure against chosen plaintext attacks,
provided the adversary can only learn 
$q \ll n^{\frac{1}{2} - \epsilon}$ evaluations of the PRP
\cite{patarin2003luby}.

We have already demonstrated that no information, including no
evaluations of the PRP, is leaked in the SqrtORAM.shuffle.
Therefore, the only evaluations of the PRP that the adversary may
learn is the $q$ evaluations of the PRP.
For a sufficiently small value of $c$ (not the $c$ from the implementation)
this is therefore secure from Patarin's result.

Since each shuffle picks new OPRFs and therefore a new PRP,
any information learned about a previous PRP will not help
the adversary distinguish subsequent PRPs from a random permutation.
\end{proof}