Paper 2023/748

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

Shiyao Chen, Nanyang Technological University
Chun Guo, Shandong University
Jian Guo, Nanyang Technological University
Li Liu, Shandong University
Meiqin Wang, Shandong University
Puwen Wei, Shandong University
Zeyu Xu, Shandong University

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.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in TOSC 2023
Symmetric-KeyCryptanalysisProofMPC/FHE/ZK-Friendly PrimitivesGeneralized FeistelGMiMC
Contact author(s)
shiyao chen @ ntu edu sg
mqwang @ sdu edu cn
2023-05-25: approved
2023-05-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shiyao Chen and Chun Guo and Jian Guo and Li Liu and Meiqin Wang and Puwen Wei and Zeyu Xu},
      title = {Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives},
      howpublished = {Cryptology ePrint Archive, Paper 2023/748},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.