Paper 2026/1154

Leakage-Tolerant Circuits Against AC0 Leakage

Abstract

A leakage-tolerant circuit (LTC) can be viewed as a black-box implementation of a given functionality f with respect to a leakage class L in the sense that any leakage function L ∈ L applied to the circuit’s internal wires can be simulated by a similar leakage function L′ ∈L applied only to the circuit’s inputs and outputs. Previous works have demonstrated extensive applications of LTCs in constructing variants of leakage-resilient circuits (LRC): black-box construction of both stateless and stateful LRCs, and construction of deterministic stateful LRCs which only require external fresh randomness in the first invocation. However, feasibility results for LTCs are still limited to simple leakage classes, including only probing leakage, depth-1 AC0 leakage, and parity leakage. In this work, we instantiate the study of constructing LTCs and deterministic stateful LRCs against AC0 leakage, obtaining the following results: – We present the first construction of LTCs against generic AC0 leakage. As a corollary, we also construct LTCs against parity leakage with efficient simulation, refuting a conjecture proposed by Ishai and Song (Eurocrypt 2024). – We provide a generic framework to convert LTCs into computationally secure deterministic LRCs assuming one-way functions, and instantiate the paradigm for k-CNF leakage (with a sufficiently small k). This is the first instance of deterministic stateful LRCs against non-decomposable leakage.