Paper 2015/567
Key-Recovery Attack on the ASASA Cryptosystem with Expanding S-boxes
Henri Gilbert, 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
Note: s/SASAS/ASASA/ in the introduction.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published by the IACR in CRYPTO 2015
- Keywords
- multivariate cryptographypolynomialscryptanalysis
- Contact author(s)
- jerome plut @ ssi gouv fr
- History
- 2015-06-17: received
- Short URL
- https://ia.cr/2015/567
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/567,
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},
url = {https://eprint.iacr.org/2015/567}
}
