The Cube/AIDA algebraic attacks: generalisations and combinatorial results

18 May 2016
The cube attack of Dinur and Shamir and the AIDA attack of Vielhaber have been used successfully on 
reduced round versions of the Trivium stream cipher and a few other ciphers. 
These attacks can be viewed in the framework of higher order differentiation, as introduced by Lai in 
the cryptographic context. We generalise these attacks from the binary case to general finite fields, 
showing that we would need to differentiate several times with respect to each variable in order to have
a reasonable chance of a successful attack.
We also investigate the notion of “fast points” for a binary polynomial function f  
(i.e. vectors such that the derivative of f with respect to this vector has a lower 
than expected degree). These were  introduced by Duan and Lai, motivated by the fact that higher order 
differential attacks are usually more efficient if they use such points. The number of functions which 
admit fast points were computed by Duan et al in a few particular cases; we give explicit formulae for 
all remaining cases and discuss the cryptographic significance of these results.
  • Cryptography Seminar