Paper 2015/221

Tighter, faster, simpler side-channel security evaluations beyond computing power

Daniel J. Bernstein, Tanja Lange, and Christine van Vredendaal


A Eurocrypt 2013 paper "Security evaluations beyond computing power: How to analyze side-channel attacks you cannot mount?" by Veyrat-Charvillon, Gérard, and Standaert proposed a "Rank Estimation Algorithm" (REA) to estimate the difficulty of finding a secret key given side-channel information from independent subkeys, such as the 16 key bytes in AES-128 or the 32 key bytes in AES-256. The lower and upper bounds produced by the algorithm are far apart for most key ranks. The algorithm can produce tighter bounds but then becomes exponentially slower; it also becomes exponentially slower as the number of subkeys increases. This paper introduces two better algorithms for the same problem. The first, the "Extended Rank Estimation Algorithm" (EREA), is an extension of REA using statistical sampling as a second step to increase the speed of tightening the bounds on the rank. The second, the "Polynomial Rank Outlining Algorithm" (PRO), is a new approach to computing the rank. PRO can handle a much larger number of subkeys efficiently, is easy to implement in a computer-algebra system such as Sage, and produces much tighter bounds than REA in less time.

Available format(s)
Publication info
Preprint. MINOR revision.
symmetric cryptographyside-channel attacksranking
Contact author(s)
authorcontact-pro @ box cr yp to
2015-07-02: revised
2015-03-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel J.  Bernstein and Tanja Lange and Christine van Vredendaal},
      title = {Tighter, faster, simpler side-channel security evaluations beyond computing power},
      howpublished = {Cryptology ePrint Archive, Paper 2015/221},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.