Paper 2015/567 Original: eprint.iacr.org/2015/567 ↗
Key-Recovery Attack on the ASASA Cryptosystem with Expanding S-boxes
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}$.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2015-06-17: last updated
- 2015-06-17: published
- Short URL
- https://ia.cr/2015/567
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}