Paper 2023/748

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

Abstract

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