Cryptology ePrint Archive: Report 2015/567

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

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

Abstract: 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}$.

Category / Keywords: public-key cryptography / multivariate cryptography,polynomials,cryptanalysis

Original Publication (in the same form): IACR-CRYPTO-2015

Date: received 9 Jun 2015, last revised 15 Jun 2015

Contact author: jerome plut at ssi gouv fr

Available format(s): PDF | BibTeX Citation

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

Version: 20150617:002401 (All versions of this report)

Short URL: ia.cr/2015/567

Discussion forum: Show discussion | Start new discussion