Garbled circuits, introduced in the seminal work of Yao (FOCS, 1986), have received considerable attention in the boolean setting due to their efficiency and application to round-efficient secure computation. In contrast, arithmetic garbling schemes have received much less scrutiny. The main efficiency measure of garbling schemes is their rate, defined as the bit size of each gate’s output divided by the size of the (amortized) garbled gate. Despite recent progress, state-of-the-art garbling schemes for arithmetic circuits suffer from important limitations: all existing schemes are either restricted to B-bounded integer arithmetic circuits (a computational model where the arithmetic is performed over \(\mathbb {Z}\) and correctness is only guaranteed if no intermediate computation exceeds the bound B) and achieve constant rate only for very large bounds \(B = 2^{\varOmega (\lambda ^3)}\) , or have a rate at most \(O(1/\lambda )\) otherwise, where \(\lambda \) denotes a security parameter. In this work, we improve this state of affairs in both settings.

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

Breaking the  \(1/\lambda \) -Rate Barrier for Arithmetic Garbling

  • Geoffroy Couteau,
  • Carmit Hazay,
  • Aditya Hegde,
  • Naman Kumar

摘要

Garbled circuits, introduced in the seminal work of Yao (FOCS, 1986), have received considerable attention in the boolean setting due to their efficiency and application to round-efficient secure computation. In contrast, arithmetic garbling schemes have received much less scrutiny. The main efficiency measure of garbling schemes is their rate, defined as the bit size of each gate’s output divided by the size of the (amortized) garbled gate. Despite recent progress, state-of-the-art garbling schemes for arithmetic circuits suffer from important limitations: all existing schemes are either restricted to B-bounded integer arithmetic circuits (a computational model where the arithmetic is performed over \(\mathbb {Z}\) and correctness is only guaranteed if no intermediate computation exceeds the bound B) and achieve constant rate only for very large bounds \(B = 2^{\varOmega (\lambda ^3)}\) , or have a rate at most \(O(1/\lambda )\) otherwise, where \(\lambda \) denotes a security parameter. In this work, we improve this state of affairs in both settings.