CryptoDB
PicoGRAM: Practical Garbled RAM from Decisional Diffie-Hellman
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | 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. |
BibTeX
@inproceedings{crypto-2025-35687,
title={PicoGRAM: Practical Garbled RAM from Decisional Diffie-Hellman},
publisher={Springer-Verlag},
author={Tianyao Gu and Afonso Tinoco and Sri Harish Govinda Rajan and Elaine Shi},
year=2025
}