International Association
for Cryptologic Research

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