Key-Recovery Attacks on <Emphasis FontCategory="SansSerif">ASASA</Emphasis> |
| |
Authors: | Brice Minaud Patrick Derbez Pierre-Alain Fouque Pierre Karpman |
| |
Affiliation: | 1.Université de Rennes 1,Rennes,France;2.Institut Universitaire de France,Paris,France;3.Inria,Saclay,France;4.Nanyang Technological University,Singapore,Singapore |
| |
Abstract: | The \(\mathsf {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 \(\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 instances claiming 64 bits of security under one minute on a laptop computer. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|