An Analytic Expression of the Key Rank and a Saddle-Point Approximation
TL;DR
The partition function of the knapsack problem, which is equivalent to the key rank, is derived with an analytic expression and used to prove the mathematical equivalence between the knapsack and histogram-based methods.
Abstract
Key ranking is a critical subject for evaluators since it measures the remaining complexity after a side-channel attack without the need to implement the key enumeration algorithm. This paper proposes a novel method based on the knapsack counting problem. While the existing literature proposes a solution of this problem with an algorithm originating from linear programming, we propose a new computation inspired by a recent work in statistical physics. The partition function of the knapsack problem, which is equivalent to the key rank, is derived with an analytic expression. This is used to prove the mathematical equivalence between the knapsack and histogram-based methods. In addition, a saddle-point approximation of the key rank is computed from the analytic expression. A very simple mathematical formula is derived. Simulation results show that the approximation is very tight. In addition, the execution time of the approximation is fast and linear in the key size, making it suitable for scaling to very large keys.