We introduce a general template for building garbled circuits with low communication, assuming decisional composite residuosity (DCR) and a circular security assumption. For the case of layered Boolean circuits, we can garble a circuit of size s with communication proportional to \(O(s/\log \log s)\) bits, plus an additive factor that is polynomial in the security parameter. For layered arithmetic circuits with B-bounded integer computation, we obtain a similar result: the garbled arithmetic circuit has size \(O(s/\log \log s) \cdot (\lambda + \log B)\) bits, where \(\lambda \) is the security parameter. In both cases, we can remove the circular security assumption by adding a term proportional to the circuit depth. These are the first constructions of general-purpose, garbled circuits with sublinear size, without relying on heavy tools like indistinguishability obfuscation or attribute-based and fully homomorphic encryption. To achieve these results, our main technical tool is a new construction of a form of homomorphic secret sharing (HSS) where some of the inputs are semi-private, that is, known to one of the evaluating parties. Through a new relinearisation technique that allows performing arbitrary additions and multiplications on semi-private shares, we build such an HSS scheme that supports evaluating any function of the form \(C(x) \cdot C'(y)\) , where C is any polynomially-sized circuit applied to the semi-private input y, and \(C'\) is a restricted-multiplication (or, NC1) circuit applied to the private input x. This significantly broadens the expressiveness of prior known HSS constructions.

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

Silent Circuit Relinearisation: Sublinear-Size (Boolean and Arithmetic) Garbled Circuits from DCR

  • Pierre Meyer,
  • Claudio Orlandi,
  • Lawrence Roy,
  • Peter Scholl

摘要

We introduce a general template for building garbled circuits with low communication, assuming decisional composite residuosity (DCR) and a circular security assumption. For the case of layered Boolean circuits, we can garble a circuit of size s with communication proportional to \(O(s/\log \log s)\) bits, plus an additive factor that is polynomial in the security parameter. For layered arithmetic circuits with B-bounded integer computation, we obtain a similar result: the garbled arithmetic circuit has size \(O(s/\log \log s) \cdot (\lambda + \log B)\) bits, where \(\lambda \) is the security parameter. In both cases, we can remove the circular security assumption by adding a term proportional to the circuit depth. These are the first constructions of general-purpose, garbled circuits with sublinear size, without relying on heavy tools like indistinguishability obfuscation or attribute-based and fully homomorphic encryption. To achieve these results, our main technical tool is a new construction of a form of homomorphic secret sharing (HSS) where some of the inputs are semi-private, that is, known to one of the evaluating parties. Through a new relinearisation technique that allows performing arbitrary additions and multiplications on semi-private shares, we build such an HSS scheme that supports evaluating any function of the form \(C(x) \cdot C'(y)\) , where C is any polynomially-sized circuit applied to the semi-private input y, and \(C'\) is a restricted-multiplication (or, NC1) circuit applied to the private input x. This significantly broadens the expressiveness of prior known HSS constructions.