Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives

Symmetric-key primitives designed over the prime field F-p with odd characteristics, rather than the traditional F-2(n) , are becoming the most popular choice for MPC/FHE/ZK-protocols for better efficiencies. However, the security of F-p is less understood as there are highly nontrivial gaps when extending the cryptanalysis tools and experiences built on F-2(n) in the past few decades to F-p. At CRYPTO 2015, Sun et al. established the links among impossible differential, zero-correlation linear, and integral cryptanalysis over F-2(n) from the perspective of distinguishers. In this paper, following the definition of linear correlations over Fp by Baign & egrave;res, Stern and Vaudenay at SAC 2007, we successfully establish comprehensive links over F-p, by reproducing the proofs and offering alternatives when necessary. Interesting and important differences between F-p and F-2(n) are observed.- Zero-correlation linear hulls can not lead to integral distinguishers for some cases over F-p, while this is always possible over 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 F-p. It should be noted that all these distinguishers do not invalidate GMiMC's security claims.The development of the theories over 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 F-p field, which we believe will provide useful guides for future cryptanalysis and design.