International Association
for Cryptologic Research

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.