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