Garbled RAM

A garbled RAM scheme garbles a database $D$, a RAM program $P$ and an input $x$ so that evaluating the garbled program, with random access to the garbled database, yields $P^D(x)$ and reveals nothing else, the access pattern included, at a cost polylogarithmic in $|D|$ per step of $P$.

Syntax

A garbled RAM scheme is a tuple of efficient algorithms $\Pi =(\mathsf{GData},\mathsf{GProg},\mathsf{GInput},\mathsf{GEval})$:

• $\mathsf{GData}(1^{\lambda },D)\to (\tilde{D},s)$, a randomized function garbling a database $D$ into a garbled database $\tilde{D}$ and a secret $s$.
• $\mathsf{GProg}(1^{\lambda },1^{\log |D|},1^t,P,s)\to (\tilde{P},s_{\mathrm{in}})$, a randomized function garbling a RAM program $P$ with running time $t$ under $s$, outputting a garbled program $\tilde{P}$ and an input key $s_{\mathrm{in}}$.
• $\mathsf{GInput}(1^{\lambda },x,s_{\mathrm{in}})\to \tilde{x}$, a randomized function garbling an input $x$.
• ${\mathsf{GEval}}^{\tilde{D}}(\tilde{P},\tilde{x})\to y$, a function with random access to $\tilde{D}$, outputting $y$.

The scheme is efficient if $|\tilde{D}|=|D|\cdot \mathrm{poly}(\lambda ,\log |D|)$ and $\mathsf{GProg}$, $\mathsf{GInput}$ and $\mathsf{GEval}$ run in time $\mathrm{poly}(\lambda )\cdot t\cdot \mathrm{polylog}|D|$ for a program $P$ with running time $t$. Without this requirement, unrolling $P$ into a circuit of size $\tilde{O}(t\cdot |D|)$ and garbling it would be an instance — folklore.

Properties

Correctness

A garbled RAM scheme $\Pi$ is $(1-\epsilon )$-correct if for all $\lambda \in \mathbb{N}$, all databases $D$, programs $P$ with running time $t$ and inputs $x$,

$$\mathrm{Pr}\left[{\mathsf{GEval}}^{\tilde{D}}(\tilde{P},\tilde{x})=P^D(x)\right]\ge 1-\epsilon ,$$

over the coins of $\mathsf{GData}$, $\mathsf{GProg}$ and $\mathsf{GInput}$. When $\epsilon =0$, we say $\Pi$ is perfectly correct.

Security

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{gram}}_{\Pi,\calA,\Sim}(\secpar)$}
\begin{algorithmic}
\State $(D, P, t, x, \stA) \gets \calA(1^\secpar)$; $b \getsr \bits$
\Comment{$P^D(x)$ halts within $t$ steps}
\State $(\tilde{D}_0, s) \gets \GData(1^\secpar, D)$
\State $(\tilde{P}_0, s_{\mathrm{in}}) \gets \GProg(1^\secpar, 1^{\log |D|}, 1^t, P, s)$; $\tilde{x}_0 \gets \GInput(1^\secpar, x, s_{\mathrm{in}})$
\State $(\tilde{D}_1, \tilde{P}_1, \tilde{x}_1) \gets \Sim(1^\secpar, |D|, |P|, |x|, t, P^D(x))$
\State $b' \gets \calA(\stA, \tilde{D}_b, \tilde{P}_b, \tilde{x}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A garbled RAM scheme $\Pi$ is secure if it is $(1-\mathrm{negl}(\lambda ))$-correct and there is an efficient $\mathcal{S}$ such that for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\Pi ,\mathcal{A},\mathcal{S}}^{\mathrm{gram}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\Pi ,\mathcal{A},\mathcal{S}}^{\mathrm{gram}}(\lambda )=1\right]-1\right|$$

is negligible. The simulator sees only $|D|$, $|P|$, $|x|$, $t$ and the output, so the garbling also hides the access pattern of $P$; this is the full security of LO13 and GHL+14.

Variations

Persistent database

Several RAM programs, garbled one after another, run in sequence on one garbled database, each seeing the database the previous ones left — GLOS15, GLO15.

Other results

• Garbled RAM with $\mathrm{poly}(\lambda )\cdot \mathrm{polylog}|D|$ overhead exists if IBE does (IBE ⇒ garbled RAM) — GHL+14.
• Garbled RAM with polylogarithmic overhead and a persistent database exists if one-way functions do, using them only as a black box (OWF ⇒ garbled RAM (black-box)) — GLO15; a construction using them in a non-black-box way came first — GLOS15.

Participates in

Produces Garbled RAM

• IBE ⇒ garbled RAM
• OWF ⇒ garbled RAM (black-box)