Higher order differentiation over finite fields with applications to generalising the cube attack
Ana Sălăgean, R. Winter, Matei Mandache-Sălăgean, Raphaël C.‐W. Phan · Designs Codes and Cryptography · 2016
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 of Dinur and Shamir and the AIDA attack of Vielhaber. All of the above have been developed for the binary case. We examine differentiation in larger fields, starting with the field $$\mathrm {GF}(p)$$ of integers modulo a prime p, and apply these techniques to generalising the cube attack to $$\mathrm {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). Connections to the Moebius/Reed Muller Transform over $$\mathrm {GF}(p)$$ are also examined. Finally we describe differentiation over finite fields $$\mathrm {GF}(p^s)$$ with $$p^s$$ elements and show that it can be reduced to differentiation over $$\mathrm {GF}(p)$$ , so a cube attack over $$\mathrm {GF}(p^s)$$ would be equivalent to cube attacks over $$\mathrm {GF}(p)$$ .