English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The problem MQ of solving a system of multivariate quadratic equations over a finite field is relevant to the security of AES and for several public key cryptosystems. For example Sflash, the fastest known signature scheme (cf. [1]), is based on MQ equations over GF(27), and Patarin’s 500 $ HFE Challenge 2 is over GF(24). Similarly, the fastest alleged algebraic attack on AES due to Courtois, Pieprzyk, Murphy and Robshaw uses a MQ system over GF(28).   At present very little is known about practical solvability of such systems of equations over GF(2 k ). The XL algorithm for Eurocrypt 2000 was initially studied over GF(p), and only recently in two papers presented at CT-RSA’02 and ICISC’02 the behaviour of XL is studied for systems of equations over GF(2). In this paper we show (as expected) that XL over GF(2 k ), k>1 (never studied so far) does not always work very well. The reason is the existence of additional roots to the system in the extension field, which is closely related to the remark made by Moh, claiming that the XSL attack on AES cannot work. However, we explain that, the specific set of equations proposed by Murphy and Robshaw already contains a structure that removes the problem. From this, we deduce a method to modify XL so that it works much better over GF(2 k ). In addition we show how to break the signature scheme Sflash-v2 recently selected by the European consortium Nessie, by three different methods derived from XL. Our fastest attack is in 258. All the three attacks apply also to HFE Challenge 2, and our best attack is in 263.

Algebraic Attacks over GF(2 k ), Application to HFE Challenge 2 and Sflash-v2