Cryptology ePrint Archive: Report 2013/815
Iterated group products and leakage resilience against NC^1
Abstract: We show that if NC^1 \neq L, then for every element g of the alternating group A_t, circuits of depth O(log t) cannot distinguish between a uniform vector over (A_t)^t with product = g 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 \neq L). For context, leakage from NC^1 breaks nearly all previous constructions, and security against leakage from P is impossible.
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.
Category / Keywords: leakage-resilient cryptography; iterated group products
Original Publication (in the same form): ITCS 2014
Date: received 3 Dec 2013, last revised 3 Dec 2013
Contact author: enmiles at ccs neu edu
Available format(s): PDF | BibTeX Citation
Version: 20131206:202242 (All versions of this report)
Short URL: ia.cr/2013/815
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]