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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

PicoGRAM: Practical Garbled RAM from Decisional Diffie-Hellman

  • Tianyao Gu,
  • Afonso Tinoco,
  • Sri Harish G. Rajan,
  • Elaine Shi

摘要

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.