CryptoDB
Leakage-Tolerant Circuits
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2024 |
| Abstract: | A {\em 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 \cal L$ to the wires of $C$ reveals essentially nothing about $x$. A {\em 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 \cal L$ to $x$ and $y$ alone. Thus, $C$ is as secure as an ideal hardware implementation of $f$ with respect to leakage from $\cal L$. Leakage-resilient circuits were constructed for low-complexity classes $\cal L$, including (length-$t$ output) $\mathcal{AC}0$ functions, parities, and functions with bounded communication complexity. In contrast, leakage-{\em tolerant} circuits were only known for the simple case of {\em probing} leakage, where $L$ outputs the values of $t$ wires in $C$. We initiate a systematic study of leakage-tolerant circuits for natural classes $\cal L$ of {\em global} leakage functions, obtaining the following main results. \begin{itemize} \item {\bf Leakage-tolerant circuits for depth-1 leakage.} Every circuit $C_f$ for $f$ can be efficiently compiled into an $\cal L$-tolerant circuit $C$ for $f$, where $\cal L$ includes all leakage functions $L$ that output either $t$ {\em parities} or $t$ {\em disjunctions} (alternatively, conjunctions) of any number of wires or their negations. In the case of parities, our simulator runs in $2^{O(t)}$ time. We provide partial evidence that this may be inherent. \item {\bf Application to stateful leakage-resilient circuits.} Using a general transformation from leakage-tolerant circuits, we obtain the first construction of {\em stateful} $t$-leakage-resilient circuits that tolerate a {\em continuous} parity leakage, and the first such construction for disjunction/conjunction leakage in which the circuit size grows sub-quadratically with $t$. Interestingly, here we can obtain $\poly(t)$-time simulation even in the case of parities. \end{itemize} |
BibTeX
@inproceedings{eurocrypt-2024-33871,
title={Leakage-Tolerant Circuits},
publisher={Springer-Verlag},
author={Yuval Ishai and Yifan Song},
year=2024
}