Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives
Symmetric-key primitives designed over the prime field Fp with odd characteristics, rather than the traditional Fn2 , are becoming the most popular choice for MPC/FHE/ZK-protocols for better efficiencies. However, the security of Fp is less understood as there are highly nontrivial gaps when extend...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2023-06-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/10981 |
| _version_ | 1827923443276840960 |
|---|---|
| author | Shiyao Chen Chun Guo Jian Guo Li Liu Meiqin Wang Puwen Wei Zeyu Xu |
| author_facet | Shiyao Chen Chun Guo Jian Guo Li Liu Meiqin Wang Puwen Wei Zeyu Xu |
| author_sort | Shiyao Chen |
| collection | DOAJ |
| description |
Symmetric-key primitives designed over the prime field Fp with odd characteristics, rather than the traditional Fn2 , are becoming the most popular choice for MPC/FHE/ZK-protocols for better efficiencies. However, the security of Fp is less understood as there are highly nontrivial gaps when extending the cryptanalysis tools and experiences built on Fn2 in the past few decades to Fp.
At CRYPTO 2015, Sun et al. established the links among impossible differential, zero-correlation linear, and integral cryptanalysis over Fn2 from the perspective of distinguishers. In this paper, following the definition of linear correlations over Fp by Baignères, Stern and Vaudenay at SAC 2007, we successfully establish comprehensive links over Fp, by reproducing the proofs and offering alternatives when necessary. Interesting and important differences between Fp and Fn2 are observed.
- Zero-correlation linear hulls can not lead to integral distinguishers for some cases over Fp, while this is always possible over Fn2
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 Fp. It should be noted that all these distinguishers do not invalidate GMiMC’s security claims.
The development of the theories over Fp behind these links, and properties identified (be it similar or different) will bring clearer and easier understanding of security of primitives in this emerging Fp field, which we believe will provide useful guides for future cryptanalysis and design.
|
| first_indexed | 2024-03-13T04:57:58Z |
| format | Article |
| id | doaj.art-ae3a35508e9d4b63b21c0d9791b8a804 |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-03-13T04:57:58Z |
| publishDate | 2023-06-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-ae3a35508e9d4b63b21c0d9791b8a8042023-06-17T15:51:16ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2023-06-012023210.46586/tosc.v2023.i2.132-175Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key PrimitivesShiyao Chen0Chun Guo1Jian Guo2Li Liu3Meiqin Wang4Puwen Wei5Zeyu Xu6Strategic Centre for Research in Privacy-Preserving Technologies and Systems, Nanyang Technological University, Singapore, Singapore; Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore; School of Cyber Science and Technology, Shandong University, Qingdao, ChinaSchool of Cyber Science and Technology, Shandong University, Qingdao, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao, China; Shandong Research Institute of Industrial Technology, Jinan, ChinaDivision of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, SingaporeSchool of Cyber Science and Technology, Shandong University, Qingdao, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao, ChinaSchool of Cyber Science and Technology, Shandong University, Qingdao, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao, China; Quan Cheng Laboratory, Jinan, ChinaSchool of Cyber Science and Technology, Shandong University, Qingdao, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao, China; Quan Cheng Laboratory, Jinan, ChinaSchool of Cyber Science and Technology, Shandong University, Qingdao, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao, China Symmetric-key primitives designed over the prime field Fp with odd characteristics, rather than the traditional Fn2 , are becoming the most popular choice for MPC/FHE/ZK-protocols for better efficiencies. However, the security of Fp is less understood as there are highly nontrivial gaps when extending the cryptanalysis tools and experiences built on Fn2 in the past few decades to Fp. At CRYPTO 2015, Sun et al. established the links among impossible differential, zero-correlation linear, and integral cryptanalysis over Fn2 from the perspective of distinguishers. In this paper, following the definition of linear correlations over Fp by Baignères, Stern and Vaudenay at SAC 2007, we successfully establish comprehensive links over Fp, by reproducing the proofs and offering alternatives when necessary. Interesting and important differences between Fp and Fn2 are observed. - Zero-correlation linear hulls can not lead to integral distinguishers for some cases over Fp, while this is always possible over Fn2 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 Fp. It should be noted that all these distinguishers do not invalidate GMiMC’s security claims. The development of the theories over Fp behind these links, and properties identified (be it similar or different) will bring clearer and easier understanding of security of primitives in this emerging Fp field, which we believe will provide useful guides for future cryptanalysis and design. https://tosc.iacr.org/index.php/ToSC/article/view/10981Symmetric-KeyCryptanalysisProofMPC/FHE/ZK-Friendly PrimitivesGeneralized FeistelGMiMC |
| spellingShingle | Shiyao Chen Chun Guo Jian Guo Li Liu Meiqin Wang Puwen Wei Zeyu Xu Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives IACR Transactions on Symmetric Cryptology Symmetric-Key Cryptanalysis Proof MPC/FHE/ZK-Friendly Primitives Generalized Feistel GMiMC |
| title | Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives |
| title_full | Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives |
| title_fullStr | Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives |
| title_full_unstemmed | Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives |
| title_short | Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives |
| title_sort | towards the links of cryptanalytic methods on mpc fhe zk friendly symmetric key primitives |
| topic | Symmetric-Key Cryptanalysis Proof MPC/FHE/ZK-Friendly Primitives Generalized Feistel GMiMC |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/10981 |
| work_keys_str_mv | AT shiyaochen towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT chunguo towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT jianguo towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT liliu towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT meiqinwang towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT puwenwei towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT zeyuxu towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives |