International audience

Either based on voltage, LASER or electro-magnetic disturbances, fault attacks represent an ever growing threat to cryptographic implementations, all the more when multiple-fault scenarios are considered. The state-of-the-art of fault countermeasures is essentially divided into two paradigms: Detection-based and infection-based countermeasures. The simple concept of detection-based countermeasures has been proven efficient to counteract fault attacks and easily extendable to handle high-order fault models. On the other hand, the design of infective countermeasures is much more challenging since most proposals have been broken in a single-fault setting. In this paper we present a new infective countermeasure framework fit for any symmetric cryptosystem. This framework takes into account the fatal flaws of previous infective proposals. Our framework can be instantiated in various flavours depending on the context of use and the available software or hardware components. In addition, we describe how our framework can be set-up to handle high-order fault attacks. As far as we know, this is the first time an infective countermeasure proposes such a feature.

The NIST selection process for standardizing Post-Quantum Cryptography Mechanisms is currently running. Many papers already studied their theoretical security, but the resistance in deployed device has not been much investigated so far. In particular, fault attack is a serious threat for algorithms implemented in embedded devices. One particularly powerful technique is to use safe-error attacks. Such attacks exploit the fact that a specific fault may or may not lead to a faulty output depending on a secret value. In this paper, we investigate the resistance of various Post-Quantum candidates algorithms against such attacks.

The Polynomial System Solving (PoSSo) problem is a fundamental NP-Hard problem in computer algebra. Among others, PoSSo have applications in area such as coding theory and cryptology. Typically, the security of multivariate public-key schemes (MPKC) such as the UOV cryptosystem of Kipnis, Shamir and Patarin is directly related to the hardness of PoSSo over finite fields. The goal of this paper is to further understand the influence of finite fields on the hardness of PoSSo. To this end, we consider the so-called hybrid approach. This is a polynomial system solving method dedicated to finite fields proposed by Bettale, Faugère and Perret (Journal of Mathematical Cryptography, 2009). The idea is to combine exhaustive search with Gröbner bases. The efficiency of the hybrid approach is related to the choice of a trade-off between the two methods. We propose here an improved complexity analysis dedicated to quadratic systems. Whilst the principle of the hybrid approach is simple, its careful analysis leads to rather surprising and somehow unexpected results. We prove that the optimal trade-off (i.e. number of variables to be fixed) allowing to minimize the complexity is achieved by fixing a number of variables proportional to the number of variables of the system considered, denoted n. Under some natural algebraic assumption, we show that the asymptotic complexity of the hybrid approach is 2(3.31-3.62 log2(q)-1)n, where q is the size of the field (under the condition in particular that log(q) ≪ n). This is to date, the best complexity for solving PoSSo over finite fields (when q > 2). We have been able to quantify the gain provided by the hybrid approach compared to a direct Gröbner basis method. For quadratic systems, we show (assuming a natural algebraic assumption) that this gain is exponential in the number of variables. Asymptotically, the gain is 21.49n when both n and q grow to infinity and log(q) ≪ n.