Symmetric-key primitives designed over the prime field $mathbb{F}_p$ with odd characteristics, rather than the traditional $mathbb{F}_2^{n}$, are becoming the most popular choice for MPC/FHE/ZK-protocols for better efficiencies. However, the security of $mathbb{F}_p$ is less understood as there are highly nontrivial gaps when extending the cryptanalysis tools and experiences built on $mathbb{F}_2^{n}$ in the past few decades to $mathbb{F}_p$.

At CRYPTO 2015, Sun et al. established the links among impossible differential, zero-correlation linear, and integral cryptanalysis over $mathbb{F}_2^{n}$ from the perspective of distinguishers. In this paper, following the definition of linear correlations over $mathbb{F}_p$ by Baignéres, Stern and Vaudenay at SAC 2007, we successfully establish comprehensive links over $mathbb{F}_p$, by reproducing the proofs and offering alternatives when necessary. Interesting and important differences between $mathbb{F}_p$ and $mathbb{F}_2^n$ are observed.

– Zero-correlation linear hulls can not lead to integral distinguishers for some cases over $mathbb{F}_p$, while this is always possible over $mathbb{F}_2^n$ proven by Sun et al..

– When the newly established links are applied to GMiMC, its impossible differential, zero-correlation linear hull and integral distinguishers can be increased by up to 3 rounds for most of the cases, and even to an arbitrary number of rounds for some special and limited cases, which only appeared in $mathbb{F}_p$. It should be noted that all these distinguishers do not invalidate GMiMC’s security claims.

The development of the theories over $mathbb{F}_p$ behind these links, and properties identified (be it similar or different) will bring clearer and easier understanding of security of primitives in this emerging $mathbb{F}_p$ field, which we believe will provide useful guides for future cryptanalysis and design.

By admin