Paper 2015/516
Key-Recovery Attacks on ASASA
Brice Minaud, Patrick Derbez, Pierre-Alain Fouque, and Pierre Karpman
Abstract
The ASASA construction is a new design scheme introduced at Asiacrypt 2014 by Biryukov, Bouillaguet and Khovratovich. Its versatility was illustrated by building two public-key encryption schemes, a secret-key scheme, as well as super S-box subcomponents of a white-box scheme. However one of the two public-key cryptosystems was recently broken at Crypto 2015 by Gilbert, Plût and Treger. As our main contribution, we propose a new algebraic key-recovery attack able to break at once the secret-key scheme as well as the remaining public-key scheme, in time complexity 2^63 and 2^39 respectively (the security parameter is 128 bits in both cases). Furthermore, we present a second attack of independent interest on the same public-key scheme, which heuristically reduces the problem of breaking the scheme to an LPN instance with tractable parameters. This allows key recovery in time complexity 2^56. Finally, as a side result, we outline a very efficient heuristic attack on the white- box scheme, which breaks instances claiming 64 bits of security under one minute on a laptop computer.
Note: Added IACR/Springer copyright
Metadata
- Available format(s)
-
PDF
- Publication info
- A major revision of an IACR publication in ASIACRYPT 2015
- Keywords
- ASASAAlgebraic CryptanalysisMultivariate CryptographyLPN
- Contact author(s)
- brice minaud @ gmail com
- History
- 2015-11-02: last of 2 revisions
- 2015-05-29: received
- See all versions
- Short URL
- https://ia.cr/2015/516
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/516,
author = {Brice Minaud and Patrick Derbez and Pierre-Alain Fouque and Pierre Karpman},
title = {Key-Recovery Attacks on {ASASA}},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/516},
year = {2015},
url = {https://eprint.iacr.org/2015/516}
}
