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 extendin...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/171682 |
| _version_ | 1826109525831188480 |
|---|---|
| author | Chen, Shiyao Guo, Chun Guo, Jian Liu, Li Wang, Meiqin Wei, Puwen Xu, Zeyu |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Chen, Shiyao Guo, Chun Guo, Jian Liu, Li Wang, Meiqin Wei, Puwen Xu, Zeyu |
| author_sort | Chen, Shiyao |
| collection | NTU |
| 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 differen-tial, 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-10-01T02:19:39Z |
| format | Journal Article |
| id | ntu-10356/171682 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:19:39Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | ntu-10356/1716822023-12-08T07:24:57Z Towards the links of cryptanalytic methods on MPC/FHE/ZK-friendly symmetric-key primitives Chen, Shiyao Guo, Chun Guo, Jian Liu, Li Wang, Meiqin Wei, Puwen Xu, Zeyu School of Physical and Mathematical Sciences Strategic Centre for Research in Privacy-Preserving Technologies & Systems (SCRIPTS) Science::Mathematics Symmetric-Key Cryptanalysis 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 differen-tial, 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. Ministry of Education (MOE) Nanyang Technological University National Research Foundation (NRF) Published version This research is supported by the National Research Foundation, Singapore under its Strategic Capability Research Centres Funding Initiative, the Nanyang Technological University in Singapore under Start-up Grant 04INS000397C230, and Ministry of Education in Singapore under Grants RG91/20, the National Key Research and Development Program of China (Grant No. 2018YFA0704702), the National Natural Science Foundation of China(Grant No. 62032014), the Major Basic Research Project of Natural Science Foundation of Shandong Province, China (Grant No. ZR202010220025), the National Key R&D Program of China (Grant No. 2022YFB2701700), Shandong Provincial Natural Science Foundation(Grant No. ZR2020MF053) and the National Natural Science Foundation of China (Grant No. 62002202). 2023-11-06T00:52:29Z 2023-11-06T00:52:29Z 2023 Journal Article Chen, S., Guo, C., Guo, J., Liu, L., Wang, M., Wei, P. & Xu, Z. (2023). Towards the links of cryptanalytic methods on MPC/FHE/ZK-friendly symmetric-key primitives. IACR Transactions On Symmetric Cryptology, 2023(2), 132-175. https://dx.doi.org/10.46586/tosc.v2023.i2.132-175 2519-173X https://hdl.handle.net/10356/171682 10.46586/tosc.v2023.i2.132-175 2-s2.0-85162977646 2 2023 132 175 en 04INS000397C230 RG91/20 IACR Transactions on Symmetric Cryptology © 2023 The Author(s). This work is licensed under a Creative Commons Attribution 4.0 International License. application/pdf |
| spellingShingle | Science::Mathematics Symmetric-Key Cryptanalysis Chen, Shiyao Guo, Chun Guo, Jian Liu, Li Wang, Meiqin Wei, Puwen Xu, Zeyu Towards the links of cryptanalytic methods on MPC/FHE/ZK-friendly symmetric-key primitives |
| 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 | Science::Mathematics Symmetric-Key Cryptanalysis |
| url | https://hdl.handle.net/10356/171682 |
| work_keys_str_mv | AT chenshiyao towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT guochun towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT guojian towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT liuli towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT wangmeiqin towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT weipuwen towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives AT xuzeyu towardsthelinksofcryptanalyticmethodsonmpcfhezkfriendlysymmetrickeyprimitives |