Name
Abstract | ||
|---|---|---|
The $$\\mathsf {ASASA}$$ construction is a new design scheme introduced at Asiacrypt 2014 by Biruykov, 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 its security to solving an $$\\mathsf {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 an instance claiming 64 bits of security under one minute on a single desktop computer. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s00145-017-9272-x | J. Cryptology |
Keywords | DocType | Volume |
ASASA,Algebraic Cryptanalysis,Multivariate cryptography,LPN | Journal | 31 |
Issue | ISSN | Citations |
3 | 0933-2790 | 4 |
PageRank | References | Authors |
0.45 | 26 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Brice Minaud | 1 | 147 | 7.75 |
| Patrick Derbez | 2 | 136 | 10.86 |
| Pierre-Alain Fouque | 3 | 1762 | 107.22 |
| Pierre Karpman | 4 | 52 | 6.08 |