[Resource Topic] 2023/748: Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives

Welcome to the resource topic for 2023/748

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

Authors: Shiyao Chen, Chun Guo, Jian Guo, Li Liu, Meiqin Wang, Puwen Wei, Zeyu Xu


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.

ePrint: https://eprint.iacr.org/2023/748

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .