Provable Security against EDP-based Differential Cryptanalysis for Two-Round Arithmetization-Oriented SPNs with MDS Mixing

Arithmetization-oriented (AO) primitives play an important role in making modern zero-knowledge proof (ZKP) and multiparty computation (MPC) systems efficient enough for practical use. Since these primitives are relatively new, their security has not yet been studied in depth. This work therefore introduces a toolbox to address one gap in their current security analyses. The gap is that when assessing the security of AO primitives against differential cryptanalysis, only single-trail differential attacks have so far been rigorously considered. Using the toolbox, more powerful generalizations of these attacks can also be analyzed. Its main tool relates the expected differential probability (EDP) of a two-round substitution-permutation network (SPN) differential to the number of rational points on a variety. Applying this to MiMC, Jarvis, HADES, Vision, and Rescue over a native field of size q with independent round/sub-keys, we are able to prove that two rounds already provide Omega(sqrt(q)) security against what we call EDP-based differential cryptanalysis, a model that covers truncated and impossible differential attacks. We also show that this bound is tight for several primitives and parameter choices by constructing matching O(sqrt(q)) distinguishers. Finally, we demonstrate that security against single-trail differential cryptanalysis does not automatically imply security against more generalized differential attacks, and that a quick EDP-based analysis naturally rediscovers previously known subspace-trail vulnerabilities of HADES partial rounds.