PicoGRAM: Practical Garbled RAM from Decisional Diffie-Hellman
摘要
We present PicoGRAM, a practical garbled RAM (GRAM) scheme that achieves a per-instruction communication cost of \(O(\lambda \cdot (W\cdot \log N \cdot \omega (1) + \log ^3 N))\) bits, 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 enables 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\times \) to \(12.6\times \) compared to the tri-state GRAM by Heath et al., and by \(2.8\times \) to \(5.8\times \) compared to NanoGRAM by Park et al.