The Cube/AIDA algebraic attacks: generalisations and combinatorial results

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.