Iterated group products and leakage resilience against NC1
Eric Miles · 2014
We show that if NC1 ≠ L, then for every element α of the alternating group At, circuits of depth O(log t) cannot distinguish between a uniform vector over (At)t with product = α and one with product = identity. Combined with a recent construction by the author and Viola in the setting of leakage-resilient cryptography [STOC '13], this gives a compiler that produces circuits withstanding leakage from NC1 (assuming NC1 ≠ L). For context, leakage from NC1 breaks nearly all previous constructions, and security against leakage from P is impossible.