Securing Circuits and Protocols against 1/poly(k) Tampering Rate

In this work we present an efficient compiler that converts any circuit

C

into one that is resilient to tampering with 1/poly(

k

) fraction of the wires, where

k

is a security parameter

independent

of the size of the original circuit |

C

|. Our tampering model is similar to the one proposed by Ishai

et al.

(Eurocrypt, 2006) where a tampering adversary may tamper with any wire in the circuit (as long as the overall number of tampered wires is bounded), by setting it to 0 or 1, or by toggling with it. Our result improves upon that of Ishai

et al.

which only allowed the adversary to tamper with 1/|

C

| fraction of the wires.

Our result is built on a recent result of Dachman-Soled and Kalai (Crypto, 2012), who constructed tamper resilient circuits in this model, tolerating a

constant

tampering rate. However, their tampering adversary may learn logarithmically many bits of sensitive information. In this work, we avoid this leakage of sensitive information, while still allowing leakage rate that is

independent

of the circuit size. We mention that the result of Dachman-Soled and Kalai (Crypto, 2012) is only for Boolean circuits (that output a single bit), and for circuits that output

k

bits, their tampering-rate becomes 1/

O

(

k

). Thus for cryptographic circuits (that output

k

bits), our result strictly improves over (Dachman-Soled and Kalai, Crypto, 2012).

In this work, we also show how to generalize this result to the setting of two-party protocols, by constructing a general 2-party computation protocol (for any functionality) that is secure against a tampering adversary, who in addition to corrupting a party may tamper with 1/poly(

k

)-fraction of the wires of the computation of the honest party and the bits communicated during the protocol.