Paper 2016/571

Simple Key Enumeration (and Rank Estimation) using Histograms: an Integrated Approach

Romain poussier, François-Xavier Standaert, and Vincent Grosso

Abstract

The main contribution of this paper, is a new key enumeration algorithm that combines the conceptual simplicity of the rank estimation algorithm of Glowacz et al. (from FSE 2015) and the parallelizability of the enumeration algorithm of Bogdanov et al. (SAC 2015) and Martin et al. (from ASIACRYPT 2015). Our new algorithm is based on histograms. It allows obtaining simple bounds on the (small) rounding errors that it introduces and leads to straightforward parallelization. We further show that it can minimize the bandwidth of distributed key testing by selecting parameters that maximize the factorization of the lists of key candidates produced by the enumeration, which can be highly beneficial, e.g. if these tests are performed by a hardware coprocessor. We also put forward that the conceptual simplicity of our algorithm translates into efficient implementations (that slightly improve the state-of-the-art). As an additional consolidating effort, we finally describe an open source implementation of this new enumeration algorithm, combined with the FSE 2015 rank estimation one, that we make available with the paper.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CHES 2016
Keywords
Key enumerationKey rankside-channel analysis
Contact author(s)
romain poussier @ uclouvain be
History
2016-06-06: revised
2016-06-03: received
See all versions
Short URL
https://ia.cr/2016/571
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/571,
      author = {Romain poussier and François-Xavier Standaert and Vincent Grosso},
      title = {Simple Key Enumeration (and Rank Estimation) using Histograms: an Integrated Approach},
      howpublished = {Cryptology ePrint Archive, Paper 2016/571},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/571}},
      url = {https://eprint.iacr.org/2016/571}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.