International Association
for Cryptologic Research

We present PicoGRAM, a practical garbled RAM (GRAM) scheme that achieves an amortized communication cost of $O(\lambda\cdot (w\cdot \log N + \log^3 N)\cdot \omega(1))$ bits per access, where $N$ is the RAM space, $w$ is the word width, $\lambda$ is the computational security parameter, and $\omega(1)$ is an arbitrarily small super-constant factor in $N$. PicoGRAM outperforms previous state-of-the-art GRAMs both asymptotically and concretely. Our key contribution is a novel garbling scheme based on the Decisional Diffie-Hellman (DDH) assumption, which unlocks efficient Single-Instruction Multiple-Data (SIMD) operations. We implemented PicoGRAM in C++ and evaluated its performance. For $N$ ranging from $2^{10}$ to $2^{24}$, PicoGRAM reduces communication costs by $5.3\sim12.6\times$ compared to the tristate GRAM by Heath et al., and $2.8\sim5.8\times$ compared to NanoGRAM by Park et al.