Paper 2024/332

Leakage-Tolerant Circuits

Abstract

A leakage-resilient circuit for $f:\{0,1{\}}^n\to \{0,1{\}}^m$ is a randomized Boolean circuit $C$ mapping a randomized encoding of an input $x$ to an encoding of $y=f(x)$, such that applying any leakage function $L\in \mathcal{L}$ to the wires of $C$ reveals essentially nothing about $x$. A leakage-tolerant circuit achieves the stronger guarantee that even when $x$ and $y$ are not protected by any encoding, the output of $L$ can be simulated by applying some $L^{\prime }\in \mathcal{L}$ to $x$ and $y$ alone. Thus, $C$ is as secure as an ideal hardware implementation of $f$ with respect to leakage from $\mathcal{L}$. Leakage-resilient circuits were constructed for low-complexity classes $$, including (length-$$ output) $$ functions, parities, and functions with bounded communication complexity. In contrast, leakage-tolerant circuits were only known for the simple case of probing leakage, where $$ outputs the values of $$ wires in $$. We initiate a systematic study of leakage-tolerant circuits for natural classes $$ of global leakage functions, obtaining the following main results. $$ Every circuit $$ for $$ can be efficiently compiled into an $$-tolerant circuit $$ for $$, where $$ includes all leakage functions $$ that output either $$ parities or $$ disjunctions (alternatively, conjunctions) of any number of wires or their negations. In the case of parities, our simulator runs in $$ time. We provide partial evidence that this may be inherent. $$ We present a general transformation from (stateless) leakage-tolerant circuits to stateful leakage-resilient circuits. Using this transformation, we obtain the first constructions of stateful $$-leakage-resilient circuits that tolerate a continuous parity/disjunction/conjunction leakage in which the circuit size grows sub-quadratically with $$. Interestingly, here we can obtain $$-time simulation even in the case of parities.