Paper 2013/815

Iterated group products and leakage resilience against NC^1

Eric Miles

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. ITCS 2014
Keywords
leakage-resilient cryptographyiterated group products
Contact author(s)
enmiles @ ccs neu edu
History
2013-12-06: received
Short URL
https://ia.cr/2013/815
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/815,
      author = {Eric Miles},
      title = {Iterated group products and leakage resilience against NC^1},
      howpublished = {Cryptology ePrint Archive, Paper 2013/815},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/815}},
      url = {https://eprint.iacr.org/2013/815}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.