Algebraic-Differential Attacks on a Family of Arithmetization-Oriented Symmetric Ciphers

LI Zhengnan, WU Baofeng, LIN Dongdai

Journal of Systems Science & Complexity ›› 2023, Vol. 36 ›› Issue (6) : 2681-2702.

PDF(390 KB)
中国科学院数学与系统科学研究院期刊网
JSSC
PDF(390 KB)
Journal of Systems Science & Complexity ›› 2023, Vol. 36 ›› Issue (6) : 2681-2702. DOI: 10.1007/s11424-023-1511-7

Algebraic-Differential Attacks on a Family of Arithmetization-Oriented Symmetric Ciphers

Author information +
History +

Abstract

Motivated by applications in advanced cryptographic protocols, research on arithmetizationoriented symmetric primitives has been rising in the field of symmetric cryptography in recent years. In this paper, the authors focus on on the collision attacks for a family of arithmetization-oriented symmetric ciphers GMiMCHash. The authors firstly enhance the algebraically controlled differential attacks proposed by introducing more variables. Then, combining algebraic attacks and differential attacks, the authors propose algebraic-differential attacks on GMiMCHash. This attack method is shown to be effective by experiments on toy versions of GMiMCHash. The authors further introduce some tricks to reduce the complexities of algebraic-differential attacks and improve the success probability of finding collisions.

Key words

Algebraic attacks / collisions / differential attacks / GMiMCHash / Gröbner basis

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
LI Zhengnan , WU Baofeng , LIN Dongdai. Algebraic-Differential Attacks on a Family of Arithmetization-Oriented Symmetric Ciphers. Journal of Systems Science and Complexity, 2023, 36(6): 2681-2702 https://doi.org/10.1007/s11424-023-1511-7

References

[1] Aly A, Ashur T, Ben-Sasson E, et al., Design of symmetric-key primitives for advanced cryptographic protocols, IACR Trans. Symmetric Cryptol., 2020, 2020(3):1-45.
[2] Albrecht M, Rechberger C, Schneider T, et al., Ciphers for MPC and FHE, Advances in Cryptology-EUROCRYPT 2015-34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, 2015.
[3] Albrecht M, Grassi L, Rechberger C, et al., MiMC:Efficient encryption and cryptographic hashing with minimal multiplicative complexity, Advances in Cryptology-ASIACRYPT 2016-22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, 2016.
[4] Ashur T and Dhooghe S, MARVELlous:A STARK-friendly family of cryptographic primitives, 2018, https://eprint.iacr.org/2018/1098.
[5] Albrecht M, Grassi L, Perrin L, et al., Feistel structures for MPC, and more, Computer Security-ESORICS 2019-24th European Symposium on Research in Computer Security, Luxembourg, 2019.
[6] Grassi L, Lüftenegger R, Rechberger C, et al., On a generalization of substitution-permutation networks:The HADES design strategy, Advances in Cryptology-EUROCRYPT 2020-39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, 2020.
[7] Canteaut A, Beyne T, Dinuret I, et al., Report on the security of stark-friendly hash functions (version 2.0), 2020, https://hal.inria.fr/hal-02883253/document.
[8] Dinur I, Liu Y, Meier W, et al., Optimized interpolation attacks on LowMC, Advances in Cryptology-ASIACRYPT 2015-21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, 2015.
[9] Dobraunig C, Eichlseder M, and Mendel F, Higher-order cryptanalysis of LowMC, Information Security and Cryptology-ICISC 2015-18th International Conference, Seoul, 2015.
[10] Rechberger C, Soleimany H, and Tiessen T, Cryptanalysis of low-data instances of full LowMCv2, IACR Trans. Symmetric Cryptol., 2018, 2018(3):163-181.
[11] Banik S, Barooti K, Durak F, et al., Cryptanalysis of LowMC instances using single plaintext/ciphertext pair, IACR Trans. Symmetric Cryptol., 2020, 2020(4):130-146.
[12] Albrecht M, Cid C, Grassi L, et al., Algebraic cryptanalysis of STARK-friendly designs:Application to MARVELlous and MiMC, Advances in Cryptology-ASIACRYPT 2019-25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, 2019.
[13] Li C and Preneel B, Improved interpolation attacks on cryptographic primitives of low algebraic degree, Selected Areas in Cryptography-SAC 2019-26th International Conference, Waterloo, 2019.
[14] Roy A, Andreeva E, and Sauer J, Interpolation cryptanalysis of unbalanced feistel networks with low degree round functions, Selected Areas in Cryptography-SAC 2020-27th International Conference, Halifax, 2020.
[15] Beyne T, Canteaut A, Dinur I, et al., Out of oddity-new cryptanalytic techniques against symmetric primitives optimized for integrity proof systems, Advances in Cryptology-CRYPTO 2020-40th Annual International Cryptology Conference, Santa Barbara, 2020.
[16] Eichlseder M, Grassi L, Lüftenegger R, et al., An algebraic attack on ciphers with low-degree round functions:Application to full MiMC, Advances in Cryptology-ASIACRYPT 2020-26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, 2020.
[17] Bertoni G, Daemen J, Peeters M, et al., On the indifferentiability of the sponge construction, Advances in Cryptology-EUROCRYPT 2008-27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, 2008.
[18] Sun Y and Wang D, The F5 algorithm in Buchberger's style, Journal of Systems Science & Complexity, 2011, 24(6):1218-1231.
[19] Wang M, Wang X, and Hui L, Differential-algebraic cryptanalysis of reduced-round of serpent- 256, Sci. China Inf. Sci., 2010, 53:546-556.
[20] Lu D, Sun Y, and Wang D, A survey on algorithms for computing comprehensive Gröbner systems and comprehensive Gröbner bases, Journal of Systems Science & Complexity, 2019, 32(1):234- 255.

Funding

This research was supported by the National Natural Science Foundation of China under Grant No. 61972393 and the Climbing Program from Institute of Information Engineering CAS under Grant No. E3Z0221112.
PDF(390 KB)

154

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉