primitives.tex

\section{Primitives}

In this section we describe a number of existing primitives which are
used in our ORAM construction.

\subsection{Oblivious Pseudo-Random Function}

A Pseudo-Random Function (PRF) is a keyed function
$F: [\prfSize] \times \mathcal{K} \rightarrow [t]$, 
where $\mathcal{K}$ is the set of possible keys.
It has the property that
any party possessing the key can efficiently compute the function,
but any party who does not possess the key
will not be able to distinguish the output from a random value
(with high probability).
An Oblivious PRF is one in which this computation is performed
as a secure multiparty computation.

For this application it is in fact sufficient to use the simplest possible
OPRF, namely a look-up table on random values.
This is somewhat inefficient in that 
initialization requires generating and storing 
$\prfSize$ random $\log{t}$-bit secret-shared numbers
and OPRF evaluations on secret inputs requires 
$\prfSize$ secure-comparisons and $\prfSize$ muxes. 
However, it has the benefit that OPRF evaluations on 
\emph{public} inputs have constant cost.

Of course, other OPRFs may be more efficient and since the design
is modular they can easily replace this construction.

\begin{algorithm}
\caption{OPRF}
\label{alg:oprf}
\begin{algorithmic}[1]

\Procedure{OPRF.init}{\prfSize, t}
\For{$i \gets 1$  to \prfSize} 
    \State $table[i] \gets^r [t]$
\EndFor
\State \textbf{return} self
\EndProcedure

\State

\Procedure{OPRF.eval\_pub}{x} \Comment{Input is public, output is secret.}
\State \textbf{return} table[x]
\EndProcedure

\State

\Procedure{OPRF.eval}{x}
\State $res \gets 0$
\For{$i \gets 1$ to \prfSize}
    \OblivIf{$i = x$}
    \State $res \gets table[i]$
    \EndOblivIf
\EndFor
\State \textbf{return} res
\EndProcedure

\end{algorithmic}
\end{algorithm}


\subsection{Oblivious Pseudo-Random Permutation}

A Pseudo-Random Permutation (PRP) is a keyed permutation
$P : [n] \times \mathcal{K} \rightarrow [n]$
that an adversary cannot distinguish from a random permutation.
A $q$-wise psuedo-random permutation is a PRP which is secure against
any adversary that can learn at most $q$ evaluations of the PRP.
On oblivious pseudo-random permutation (OPRP) is a MPC protocol
that evaluates a PRP using secret data.

For our application we want an OPRP that is $\sqrt{n}$-wise pseudo-random
on a small domain $[n]$. 
Unfortunately, we were not able to find such an OPRP, but we were able
to find something with almost this functionality.
The fact that the domain is small seems to make the construction of a PRP
more challenging and while there has been some work towards constructing these
\cite{black2002ciphers, morris2009encipher, stefanov2012fastprp},
these solutions are not very efficient.

One approach to this problem is to use a Feistel Cipher.
A Feistel Cipher is a technique for constructing a PRP from a PRF.
Namely, a PRF $F \times \mathcal{K} : [\prfSize] \rightarrow [\prfSize]$ 
can be transformed into a PRP 
$G : [\prfSize] \times [\prfSize] \times \mathcal{K} \rightarrow [\prfSize] \times [\prfSize]$. 
In our case we set $\prfSize = \sqrt{n}$ to construct a PRP on 
$[n]$ from PRFs on $[\prfSize]$.
The technique involves multiple rounds of evaluation of the following function.
Let $i = (L, R)$, where $i \in [\prfSize] \times [\prfSize]$ and $L, R \in [\prfSize]$.
Let $B_j(i) = (R, L + F_j(R))$, where $F_j$ is a OPRF.
$B_j$ is invertible and maps $[\prfSize] \times [\prfSize]$ to $[\prfSize] \times [\prfSize]$, 
so is a permutation.
However, it is clearly not pseudo-random, since the last element of $i$ 
completely reveals the first element of $B_j(i)$.
Nevertheless, for a larger number of rounds, this is $q$-wise 
pseudorandom for certain values of $q$.

The original paper that presented the Feistel cipher \cite{luby1988construct}
proved that 3 rounds were sufficient to provide statistical pseudo-randomness
for $q \ll n^{\frac{1}{4}}$.
Subsequent works examined the security for larger numbers of rounds.
Patarin showed that, for any $\epsilon > 0$,
seven rounds are sufficient to provide statistical pseudo-randomness for 
$q \leq c n^{\frac{1}{2} - \epsilon})$ for some constant $c$ 
\cite{patarin2003luby}.
Unfortunately, it is not clear what the concrete advantage of the
adversary is for a given $n$, $c$ and $\epsilon$.
We chose to keep $ROUNDS=7$ and to set $c=1$ and $\epsilon = \frac{1}{8}$.

This protocol is described as an algorithm in the following figure,
where the PRF is treated in a black-box manner.

\begin{algorithm}
\caption{OPRP}
\label{alg:oprp}
\begin{algorithmic}[1]

\Procedure{OPRP.init}{n, $F$}  \Comment{F contains ROUNDS OPRFs}
\State \textbf{return} self   \Comment{Remember initialization variables}
\EndProcedure

\State

\Procedure{OPRP.eval}{x}
\State $L_0 \gets x \bmod \sqrt{n}$
\State $R_0 \gets \lfloor \frac{x}{\sqrt{n}} \rfloor$

\For{$i \gets 1$ to $ROUNDS$}
\State $L_i \gets R_{i-1}$
\State $R_i \gets ( L_{i-1} + F_{i}.eval(R_{i-1}) ) \bmod \sqrt{n}$
\EndFor

\State $res \gets L_{ROUNDS}\sqrt{n} + R_{ROUNDS}$
\State \textbf{return} $res$
\EndProcedure

\end{algorithmic}
\end{algorithm}
\subsection{Oblivious Sorting}

Oblivious sorting is fundamental to many ORAM protocols and is often
a bottle-neck in the secure computation.
However, we can utilize the fact that every sort we do will be sorting
based on an array that contains every possible element exactly once.
Therefore, we can randomly permute the elements first,
then reveal the field to be sorted on and then sort in the clear.

The function takes at least two arguments. 
The first, $A$, is an array of the indices to be sorted on.
Their distribution (but not order) is public and there are no duplicates.
The remaining arguments are arrays of the same length as the index array,
which should be sorted according to the index array.
The protocol is presented in Figure~\ref{fig:OblivSort}.


\begin{algorithm}
\caption{oblivSort: Sort based on indexes with a public distribution}
\label{fig:OblivSort}
\begin{algorithmic}[0]

\Procedure{oblivSort}{A, B}
\State $(\hat{A} , \hat{B}) = shuffle(A, B)$
\State $\tilde{A} = reveal(\hat{A})$
\State $\bar{B} = sort(\tilde{A}, \hat{B})$
\State \textbf{return} $\bar{B}$
to be evaluated on a \emph{secret} input.
\EndProcedure

\end{algorithmic}
\end{algorithm}

\subsection{Random Shuffle}

There are many protocols for a random shuffle.
We will use a Waksman permutation network.
\footnote{Waksman permutation networks are very good for shuffling an array,
however evaluating the permutation on a particular point cannot be done
efficiently. Hence, we do not use Waksman networks to perform the ORAM permutation.}
This is a $O(n \log{n})$-sized network of switches that allows computationation
of an arbitrary permutation by setting the switch-bits appropriately.
An important observation is that setting the switch-bits randomly
does not result in a random permutation.
Therefore, for the MPC setting where at most $t$ players are dishonest,
$(t+1)$ players should each choose switch-bits and have a Waksman permutation
evaluated on the array, in turn, using these switch bits.  
In an arithmetic ciruit MPC framework, this can be done using $O( (t+1) n \log{n})$ multiplications.

\subsection{Linear ORAM}

The most basic ORAM scheme is to store all $m$ elements in an array,
access every element of the array, and keep the desired element.
This is clearly inefficient.
However, this is useful for smaller arrays.

In the ORAM scheme presented in this paper, Linear ORAM
is used to store a $\omega(\sqrt{m})$ sized stash.

For the stash application, this may be slightly optimized compared to the 
general case since the type of access (read vs write) can be public.

\begin{algorithm}
\caption{LinearORAM}
\label{alg:obliv_set}
\begin{algorithmic}[1]

\Procedure{LinearORAM.init}{$max\_size$}  

\State $stash \gets [ \bot $ for $0 \leq i < max\_size]$
\State $nElem \gets 0$
\State \textbf{return} self
\EndProcedure

\State

\Procedure{LinearORAM.add}{$(x, y)$} 
\Comment{Assumes fewer than $max\_size$ elements have already been added}
\State $stash[nElem + 1] \gets (x, y)$
\State $nElem \gets nElem + 1$
\EndProcedure

\State

\Procedure{LinearORAM.empty}{}
\State $stash \gets [ \bot $ for $0 \leq i < nElem]$
\State $nElem \gets 0$
\EndProcedure

\State

\Procedure{LinearORAM.get}{$key$}
\State $res \gets \bot$
\For{$j \gets 1$ to $nElem$}
    \State $(x, y) \gets stash[j]$
    \OblivIf{$key = x$}
        \State $res \gets y$
    \EndOblivIf
\EndFor
\State \textbf{return} res
\EndProcedure

\end{algorithmic}
\end{algorithm}