Leakage-Tolerant Computation with Input-Independent Preprocessing

Following a rich line of research on leakage-resilient cryptography, [Garg, Jain, and Sahai, CRYPTO11] and [Bitansky, Canetti, and Halevi, TCC12] initiated the study of

secure interactive protocols

in the presence of arbitrary leakage. They put forth notions of

leakage tolerance

for zero-knowledge and general secure multi-party computation that aim at capturing the best-possible security when the private inputs of honest parties are exposed to direct leakage. So far, only a handful of specific two-party functionalities have been successfully realized under the notion. General functionalities were only realized under weaker security notions [Boyle, Garg, Jain, Kalai, and Sahai, Crypto13], or relying on leakage-immune input-processing, which needs to be repeated for each and every execution [Boyle, Goldwasser, Jain, Kalai, STOC12].

We construct leakage-tolerant multi-party computation protocols for

general functions

, relying on

input-independent preprocessing

that is performed once and for-all. The protocols tolerate continual leakage, throughout an unbounded number of executions, provided that leakage is bounded within any particular execution. In the malicious setting, we also require a common reference string, and a constant fraction of honest parties.

At the core of our construction, is a tight connection between secure compilers in the Only-Computation-Leaks (OCL) model and leakage-tolerant protocols. In particular, we show that two-party leakage-tolerant protocols with input-independent preprocessing are essentially

equivalent

to two-component OCL compilers satisfying certain strong properties. We then show how to construct such

strong OCL compilers

in the plain model, with the help of

O

(1) auxliary components.