Simona Samardjiska held a seminar with Ph.D. students and researchers at the Selmer Center (University of Bergen). The topic was «Linear attacks in MQ cryptography».
In the past two decades, as a result of the advancement in quantum algorithms, the crypto community showed increasing interest in algorithms that would be potentially secure in the post quantum world. One of the possible alternatives are Multivariate Quadratic (MQ) public key cryptosystems based on the NP-hard problem of solving quadratic polynomial systems of equations over finite fields.Many different MQ schemes emerged over the years, most of which fall into two main categories – single field schemes, including UOV, Rainbow, STS, the MQQ family of cryptosystems, and mixed field schemes including C*, SFLASH, HFE. Unfortunately, most of them have been successfully cryptanalysed using three major types of attacks:
– MinRank attacks – based on the problem of finding a low rank linear combination of matrices;
– Equivalent Keys attacks – based on finding an equivalent key for the respective scheme.
– Differential attacks – based on specific invariants of the differential of a given public key.
The seminar concentrated on the MinRank attacks and Equivalent Keys attacks on single-field MQ schemes. After an introduction in the topic, the focus was focus on:
– The new attack on the MQQ family of cryptosystems, that will be presented at PKC 2015. The MQQ family of cryptosystems (the name coming from Multivariate Quadratic Quasigroups being used in the design) show especially good performance properties. In particular, the MQQ-SIG signature scheme is the fastest scheme in the ECRYPT benchmarking of cryptographic systems (eBACS). We show that both the signature scheme MQQ-SIG and the encryption scheme MQQ-ENC, although using different types of MQQs, share a common algebraic structure that introduces a weakness in both schemes. We use this weakness to mount a successful polynomial time key-recovery attack that finds an equivalent key. Our theoretical results work in characteristic 2 which is known to be the most difficult case to address in theory for MinRank attacks. Futher, the attack can be applied to any MQ scheme, that exibits linear subspaces. From a practical point of view, we are able to break an MQQ-SIG instance of 80 bits security in less than 2 days, and MQQ-ENC instances of 128 bits security in little bit over 9 days.
– The generalization of the attack on other schemes in MQ cryptography. We will show how this attack extends to a new general framework for the security of MQ schemes with respect to attacks that exploit the existence of linear subspaces. For the purpose, we have adopted the linearity measures that have been used traditionally to estimate the security of symmetric cryptographic primitives, namely, the nonlinearity measure for vectorial functions introduced by Nyberg, and the (s, t)-linearity measure introduced recently by Boura and Canteaut. We redefine some properties of MQ cryptosystems in terms of these known symmetric cryptography notions, and show that our new framework is a compact generalization of several known attacks in MQ cryptography against single field schemes. We use the framework to explain various pitfalls regarding the successfulness of these attacks. Finally, we argue that linearity can be used as a solid measure for the susceptibility of MQ schemes to these attacks, and also as a necessary tool for prudent design practice in MQ cryptography.
