Paper 2021/308

Threshold Garbled Circuits and Ad Hoc Secure Computation

Michele Ciampi, Vipul Goyal, and Rafail Ostrovsky

Abstract

Garbled Circuits (GCs) represent fundamental and powerful tools in cryptography, and many variants of GCs have been considered since their introduction. An important property of the garbled circuits is that they can be evaluated securely if and only if exactly 1 key for each input wire is obtained: no less and no more. In this work we study the case when: 1) some of the wire-keys are missing, but we are still interested in computing the output of the garbled circuit and 2) the evaluator of the GC might have both keys for a constant number of wires. We start to study this question in terms of non-interactive multi-party computation (NIMPC) which is strongly connected with GCs. In this notion there is a fixed number of parties ($n$) that can get correlated information from a trusted setup. Then these parties can send an encoding of their input to an evaluator, which can compute the output of the function. Similarly to the notion of ad hoc secure computation proposed by Beimel et al. [ITCS 2016], we consider the case when less than $n$ parties participate in the online phase, and in addition we let these parties colluding with the evaluator. We refer to this notion as Threshold NIMPC. In addition, we show that when the number of parties participating in the online phase is a fixed threshold $l\leq n$ then it is possible to securely evaluate any $l$-input function. We build our result on top of a new secret-sharing scheme (which can be of independent interest) and on the results proposed by Benhamouda, Krawczyk and Rabin [Crypto 2017]. Our protocol can be used to compute any function in NC1 in the information-theoretic setting and any function in $P$ assuming one-way functions. As a second (and main) contribution, we consider a slightly different notion of security in which the number of parties that can participate in the online phase is not specified, and can be any number $c$ above the threshold $l$ (in this case the evaluator cannot collude with the other parties). We solve an open question left open by  Beimel, Ishai and Kushilevitz [Eurocrypt 2017] showing how to build a secure protocol for the case when $c$ is constant, under the Learning with Errors assumption.

Note: Compared to the proceedings, this paper contains the full proofs of the theorems and minor differences in the main body.