Iterated group products and leakage resilience against NC^1

Abstract

We show that if NC${}^1\ne$ L, then for every element $\alpha$ of the alternating group $A_t$, circuits of depth $O(\log t)$ cannot distinguish between a uniform vector over $(A_t{)}^t$ with product $=\alpha$ 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 NC${}^1$ (assuming NC${}^1\ne$ L). For context, leakage from NC${}^1$ breaks nearly all previous constructions, and security against leakage from P is impossible. %In the multi-query setting, circuits produced by this compiler use a simple secure hardware component. We build on work by Cook and McKenzie [J.\ Algorithms '87] establishing the relationship between L $=$ logarithmic space and the symmetric group $S_t$. Our techniques include a novel algorithmic use of commutators to manipulate the cycle structure of permutations in $A_t$.

arXiv commentITCS 2014