Leakage-Tolerant Circuits

A leakage-resilient circuit for \(f:\{0,1\}^n\rightarrow \{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'\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 \(\mathcal L\) , including (length-t output) \(\mathcal{A}\mathcal{C}0\) functions, parities, and functions with bounded communication complexity. In contrast, leakage-tolerant circuits were only known for the simple case of probing leakage, where L outputs the values of t wires in C. We initiate a systematic study of leakage-tolerant circuits for natural classes \(\mathcal L\) of global leakage functions, obtaining the following main results.