Securing Circuits Against
Constant-Rate Tampering
Dana Dachman-Soled (Microsoft Research
Yael Tauman Kalai (Microsoft
Research New
Abstract:
We present a compiler that converts any circuit into one that remains secure
even if a constant fraction of its
wires are tampered with. Following the seminal work of Ishai
et al. (Eurocrypt 2006), we consider adversaries
who may choose an arbitrary set of wires to corrupt, and may set each such
wire to $0$ or to $1$, or may toggle with the wire. We prove that such
adversaries, who continuously
tamper with the circuit, can learn at most
logarithmically many bits of secret information (in addition to black-box
access to the circuit). Our results are information theoretic.