Paper 2015/567

Key-Recovery Attack on the ASASA Cryptosystem with Expanding S-boxes

Henri Gilbert, Jérôme Plût, and Joana Treger


We present a cryptanalysis of the ASASA public key cipher introduced at Asiacrypt 2014. This scheme alternates three layers of affine transformations A with two layers of quadratic substitutions S. We show that the partial derivatives of the public key polynomials contain information about the intermediate layer. This enables us to present a very simple distinguisher between an ASASA public key and random polynomials. We then expand upon the ideas of the distinguisher to achieve a full secret key recovery. This method uses only linear algebra and has a complexity dominated by the cost of computing the kernels of $2^{26}$ small matrices with entries in $\mathbb F_{16}$.

Note: s/SASAS/ASASA/ in the introduction.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in CRYPTO 2015
multivariate cryptographypolynomialscryptanalysis
Contact author(s)
jerome plut @ ssi gouv fr
2015-06-17: received
Short URL
Creative Commons Attribution


      author = {Henri Gilbert and Jérôme Plût and Joana Treger},
      title = {Key-Recovery Attack on the ASASA Cryptosystem with Expanding S-boxes},
      howpublished = {Cryptology ePrint Archive, Paper 2015/567},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.