zbMATH — the first resource for mathematics

On the leakage of corrupted garbled circuits. (English) Zbl 1421.94084
Baek, Joonsang (ed.) et al., Provable security. 12th international conference, ProvSec 2018, Jeju, South Korea, October 25–28, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11192, 3-21 (2018).
Summary: Secure two-party computation provides a way for two parties to compute a function, that depends on the two parties’ inputs, while keeping them private. Known since the 1980s, Yao’s garbled circuits appear to be a general solution to this problem, in the semi-honest model. Decades of optimizations have made this tool a very practical solution. However, it is well known that a malicious adversary could modify a garbled circuit before submitting it. Many protocols, mostly based on cut-and-choose, have been proposed to secure Yao’s garbled circuits in the presence of malicious adversaries. Nevertheless, how much an adversary can modify a circuit and make it still executable has not been studied yet. The main contribution of this paper is to prove that any modification made by an adversary is equivalent to adding/removing NOT gates arbitrarily in the original circuit, otherwise the adversary can get caught. Thereafter, we study some evaluation functions for which, even without using cut-and-choose, no adversary can gain more information about the inputs by modifying the circuit. We also give an improvement over most recent cut-and-choose solutions by requiring that different circuits of the same function are used instead of just one.
For the entire collection see [Zbl 1398.94007].
94A62 Authentication, digital signatures and secret sharing
Full Text: DOI