Profiling Deep Learning Side-channel Attacks using Multi-label against AES circuits with RSM Countermeasure

摘要

The MinRank problem is investigated as a problem relatedto rank attacks in multivariate cryptography and the decoding of rank codesin coding theory. The Kipnis-Shamir method is one of the methods tosolve the problem, and recently, significant progress has been made in itscomplexity estimation by Verbel et al. As this method reduces the problemto an MQ problem, which asks for a solution to a system of quadraticequations, its complexity depends on the solving degree of a quadraticsystem deduced from the method. A theoretical value introduced by Verbelet al. approximates the minimal solving degree of the quadratic systems inthe method although their value is defined under a certain limit for the systemconsidered. A quadratic system outside their limitation often has a largersolving degree, but the solving complexity is not always higher because ithas a smaller number of variables and equations. Thus, in order to discussthe best complexity of the Kipnis-Shamir method, a theoretical value isneeded to approximate the solving degree of each quadratic system deducedfrom the method. A quadratic system deduced from the Kipnis-Shamirmethod always has a multi-degree, and the solving complexity is influencedby this property. In this study, we introduce a theoretical value defined bysuch a multi-degree and show that it approximates the solving degree ofeach quadratic system. Thus, the systems deduced from the method arecompared, and the best complexity is discussed. As an application, for theMinRank attack using the Kipnis-Shamir method against the multivariatesignature scheme Rainbow, we show a case in which a deduced quadraticsystem outside Verbel et al.’s limitation is the best. In particular, thecomplexity estimation of the MinRank attack using the KS method againstthe Rainbow parameter sets Ⅰ, Ⅲ and Ⅴ is reduced by about 172, 140 and212 bits, respectively, from Verbel et al.’s estimation.