Higher Order Differentiation over Finite Fields with Applications to Generalising the Cube Attack
This work addresses a cryptographic security analysis problem for researchers and practitioners by extending attack techniques to non-binary fields, though it is incremental as it builds on existing differentiation concepts.
The paper tackles the problem of generalizing higher order differentiation and the cube attack from binary fields to larger finite fields like GF(p) and GF(p^m), proving theoretical results and applying them to enable differentiation multiple times per variable, unlike previous methods limited to at most once per variable.
Higher order differentiation was introduced in a cryptographic context by Lai. Several attacks can be viewed in the context of higher order differentiations, amongst them the cube attack and the AIDA attack. All of the above have been developed for the binary case. We examine differentiation in larger fields, starting with the field $GF(p)$ of integers modulo a prime $p$. We prove a number of results on differentiating polynomials over such fields and then apply these techniques to generalising the cube attack to $GF(p)$. The crucial difference is that now the degree in each variable can be higher than one, and our proposed attack will differentiate several times with respect to each variable (unlike the classical cube attack and its larger field version described by Dinur and Shamir, both of which differentiate at most once with respect to each variable). Finally we describe differentiation over finite fields $GF(p^m)$ with $p^m$ elements and prove that it can be reduced to differentiation over $GF(p)$, so a cube attack over $GF(p^m)$ would be equivalent to cube attacks over $GF(p)$.