We study the problem of constructing Boolean garbling schemes that are both succinct—with garbled circuit size significantly smaller than the original circuit—and have low-depth garbling algorithms, where the garbling process runs in parallel time logarithmic in the circuit size. Prior schemes achieve one but not the other, unless relying on indistinguishability obfuscation (iO), which is prohibitively inefficient, relies on a combination of multiple assumptions, and achieves only polynomial garbling depth \(\textsf{poly}(\lambda ,\log |C|)\) . We resolve this tension by presenting the first garbling schemes that are both succinct and admit garbling algorithms in \(\textsf{NC}^1\) , based only on standard group and lattice assumptions. Our main results include: The DDH-based one-bit-per-gate scheme has tunably small inverse polynomial correctness and privacy errors, which can be made negligible at the cost of increasing garbling depth to \(\textsf{poly}(\lambda )\) . As further extension, we also obtain the first attribute-based encryption schemes with succinct keys and low-depth key generation. At a conceptual level, our constructions are derived from a unified framework that subsumes all prior approaches to succinct garbling. It identifies the common source of high-depth garbling, and provides a general methodology for reducing garbling depth without sacrificing succinctness, applicable across different techniques and assumptions.

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

Succinct Garbled Circuits with Low-Depth Garbling Algorithms

  • Hanjun Li,
  • Huijia Lin,
  • George Lu

摘要

We study the problem of constructing Boolean garbling schemes that are both succinct—with garbled circuit size significantly smaller than the original circuit—and have low-depth garbling algorithms, where the garbling process runs in parallel time logarithmic in the circuit size. Prior schemes achieve one but not the other, unless relying on indistinguishability obfuscation (iO), which is prohibitively inefficient, relies on a combination of multiple assumptions, and achieves only polynomial garbling depth \(\textsf{poly}(\lambda ,\log |C|)\) . We resolve this tension by presenting the first garbling schemes that are both succinct and admit garbling algorithms in \(\textsf{NC}^1\) , based only on standard group and lattice assumptions. Our main results include: The DDH-based one-bit-per-gate scheme has tunably small inverse polynomial correctness and privacy errors, which can be made negligible at the cost of increasing garbling depth to \(\textsf{poly}(\lambda )\) . As further extension, we also obtain the first attribute-based encryption schemes with succinct keys and low-depth key generation. At a conceptual level, our constructions are derived from a unified framework that subsumes all prior approaches to succinct garbling. It identifies the common source of high-depth garbling, and provides a general methodology for reducing garbling depth without sacrificing succinctness, applicable across different techniques and assumptions.