{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:25:00Z","timestamp":1760149500883,"version":"build-2065373602"},"reference-count":46,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T00:00:00Z","timestamp":1691625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2022YFB2701900","62072181"],"award-info":[{"award-number":["2022YFB2701900","62072181"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Natural Science Foundation of China","award":["2022YFB2701900","62072181"],"award-info":[{"award-number":["2022YFB2701900","62072181"]}]},{"name":"Shanghai Trusted Industry Internet Software Collaborative Innovation Center","award":["2022YFB2701900","62072181"],"award-info":[{"award-number":["2022YFB2701900","62072181"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The rise of modern cryptographic protocols such as Zero-Knowledge proofs and secure Multi-party Computation has led to an increased demand for a new class of symmetric primitives. Unlike traditional platforms such as servers, microcontrollers, and desktop computers, these primitives are designed to be implemented in arithmetical circuits. In terms of security evaluation, arithmetization-oriented primitives are more complex compared to traditional symmetric cryptographic primitives. The arithmetization-oriented permutation Grendel employs the Legendre Symbol to increase the growth of algebraic degrees in its nonlinear layer. To analyze the security of Grendel thoroughly, it is crucial to investigate its resilience against algebraic attacks. This paper presents a preimage attack on the sponge hash function instantiated with the complete rounds of the Grendel permutation, employing algebraic methods. A technique is introduced that enables the elimination of two complete rounds of substitution permutation networks (SPN) in the sponge hash function without significant additional cost. This method can be combined with univariate root-finding techniques and Gr\u00f6bner basis attacks to break the number of rounds claimed by the designers. By employing this strategy, our attack achieves a gain of two additional rounds compared to the previous state-of-the-art attack. With no compromise to its security margin, this approach deepens our understanding of the design and analysis of such cryptographic primitives.<\/jats:p>","DOI":"10.3390\/sym15081563","type":"journal-article","created":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T10:11:22Z","timestamp":1691662282000},"page":"1563","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Algebraic Attacks against Grendel: An Arithmetization-Oriented Primitive with the Legendre Symbol"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8314-4402","authenticated-orcid":false,"given":"Jianqiang","family":"Ni","sequence":"first","affiliation":[{"name":"Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200062, China"}]},{"given":"Jianhui","family":"Zhang","sequence":"additional","affiliation":[{"name":"R&D Center, Shandong Luruan Digital Technology Co., Ltd., Jinan 250101, China"}]},{"given":"Gaoli","family":"Wang","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200062, China"}]},{"given":"Rui","family":"Li","sequence":"additional","affiliation":[{"name":"Inspur Academy of Science and Technology, Jinan 250014, China"}]},{"given":"Yanzhao","family":"Shen","sequence":"additional","affiliation":[{"name":"Shandong Institute of Blockchain, Jinan 250101, China"}]}],"member":"1968","published-online":{"date-parts":[[2023,8,10]]},"reference":[{"key":"ref_1","first-page":"191","article-title":"MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity","volume":"Volume 10031","author":"Cheon","year":"2016","journal-title":"Advances in Cryptology\u2014ASIACRYPT 2016, Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 4\u20138 December 2016, Proceedings, Part I"},{"key":"ref_2","first-page":"151","article-title":"Feistel Structures for MPC, and More","volume":"Volume 11736","author":"Sako","year":"2019","journal-title":"Computer Security\u2014ESORICS 2019, Proceedings of the 24th European Symposium on Research in Computer Security, Luxembourg, 23\u201327 September 2019, Proceedings, Part II"},{"key":"ref_3","first-page":"674","article-title":"On a Generalization of Substitution-Permutation Networks: The HADES Design Strategy","volume":"Volume 12106","author":"Canteaut","year":"2020","journal-title":"Advances in Cryptology\u2014EUROCRYPT 2020, Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 10\u201314 May 2020, Proceedings, Part II"},{"key":"ref_4","unstructured":"Bailey, M., and Greenstadt, R. (2021). USENIX Security 2021, Proceedings of the 30th USENIX Security Symposium, 11\u201313 August 2021, Springer. USENIX Association."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"194741","DOI":"10.1109\/ACCESS.2020.3033564","article-title":"Masta: An HE-Friendly Cipher Using Modular Arithmetic","volume":"8","author":"Ha","year":"2020","journal-title":"IEEE Access"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"30","DOI":"10.46586\/tches.v2023.i3.30-73","article-title":"Pasta: A Case for Hybrid Homomorphic Encryption","volume":"2023","author":"Dobraunig","year":"2023","journal-title":"Iacr Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref_7","first-page":"3","article-title":"Ciminion: Symmetric Encryption Based on Toffoli-Gates over Large Finite Fields","volume":"Volume 12697","author":"Canteaut","year":"2021","journal-title":"Advances in Cryptology\u2014EUROCRYPT 2021, Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 17\u201321 October 2021, Proceedings, Part II"},{"key":"ref_8","unstructured":"Yin, H., Stavrou, A., Cremers, C., and Shi, E. (2022). CCS 2022, Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, CA, USA, 7\u201311 November 2022, ACM."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"20","DOI":"10.46586\/tosc.v2022.i3.20-72","article-title":"Invertible Quadratic Non-Linear Layers for MPC-\/FHE-\/ZK-Friendly Schemes over Fnp Application to Poseidon","volume":"2022","author":"Grassi","year":"2022","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref_10","unstructured":"Szepieniec, A. (2023, June 17). On the Use of the Legendre Symbol in Symmetric Cipher Design. Paper 2021\/984. Available online: https:\/\/eprint.iacr.org\/2021\/984."},{"key":"ref_11","first-page":"163","article-title":"On the Randomness of Legendre and Jacobi Sequences","volume":"Volume 403","author":"Goldwasser","year":"1988","journal-title":"Advances in Cryptology\u2014CRYPTO 1988, Proceedings of the 8th Annual International Cryptology Conference, Santa Barbara, CA, USA, 21\u201325 August 1988, Proceedings"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1090\/S0025-5718-1992-1106978-9","article-title":"On the Distribution of Quadratic Residues and Nonresidues Modulo a Prime Number","volume":"58","author":"Peralta","year":"1992","journal-title":"Math. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"365","DOI":"10.4064\/aa-82-4-365-377","article-title":"On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol","volume":"82","author":"Mauduit","year":"1997","journal-title":"Acta Arith."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Maksymovych, V., Shabatura, M., Harasymchuk, O., Shevchuk, R., Sawicki, P., and Zajac, T. (2022). Combined Pseudo-Random Sequence Generator for Cybersecurity. Sensors, 22.","DOI":"10.3390\/s22249700"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s10998-007-4185-1","article-title":"Collision and avalanche effect in families of pseudorandom binary sequences","volume":"55","year":"2007","journal-title":"Period. Math. Hung."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Larcher, G., Pillichshammer, F., Winterhof, A., and Xing, C. (2014). Applied Algebra and Number Theory, Cambridge University Press. Number Theory.","DOI":"10.1017\/CBO9781139696456"},{"key":"ref_17","unstructured":"Khovratovich, D. (2023, June 17). Key Recovery Attacks on the Legendre PRFs within the Birthday Bound. Paper 2019\/862. Available online: https:\/\/eprint.iacr.org\/2019\/862."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"313","DOI":"10.46586\/tosc.v2020.i1.313-330","article-title":"Cryptanalysis of the Legendre PRF and Generalizations","volume":"2020","author":"Beullens","year":"2020","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"267","DOI":"10.2140\/obs.2020.4.267","article-title":"Cryptanalysis of the generalised Legendre pseudorandom function","volume":"4","author":"Kleinjung","year":"2020","journal-title":"Open Book Ser."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Seres, I.A., Horv\u00e1th, M., and Burcsi, P. (2023, June 17). The Legendre Pseudorandom Function as a Multivariate Quadratic Cryptosystem: Security and Applications. Paper 2021\/182. Available online: https:\/\/eprint.iacr.org\/2021\/182.","DOI":"10.1007\/s00200-023-00599-2"},{"key":"ref_21","unstructured":"Shallue, C.J. (2012). Permutation polynomials of finite fields. arXiv."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"5","DOI":"10.46586\/tosc.v2022.i1.5-37","article-title":"The Legendre Symbol and the Modulo-2 Operator in Symmetric Schemes over Fnp Preimage Attack on Full Grendel","volume":"2022","author":"Grassi","year":"2022","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref_23","first-page":"2","article-title":"Differential Cryptanalysis of DES-like Cryptosystems","volume":"Volume 537","author":"Menezes","year":"1990","journal-title":"Advances in Cryptology\u2014CRYPTO 1990, Proceedings of the 10th Annual International Cryptology Conference, Santa Barbara, CA, USA, 11\u201315 August 1990, Proceedings"},{"key":"ref_24","first-page":"386","article-title":"Linear Cryptanalysis Method for DES Cipher","volume":"Volume 765","author":"Helleseth","year":"1993","journal-title":"Advances in Cryptology\u2014EUROCRYPT 1993, Proceedings of the Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, 23\u201327 May 1993, Proceedings"},{"key":"ref_25","unstructured":"Ashur, T., and Dhooghe, S. (2023, June 17). MARVELlous: A STARK-Friendly Family of Cryptographic Primitives. Paper 2018\/1098. Available online: https:\/\/eprint.iacr.org\/2018\/1098."},{"key":"ref_26","first-page":"299","article-title":"Out of Oddity - New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems","volume":"Volume 12172","author":"Micciancio","year":"2020","journal-title":"Advances in Cryptology\u2014CRYPTO 2020, Proceedings of the 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, 17\u201321 August 2020, Proceedings, Part III"},{"key":"ref_27","first-page":"477","article-title":"An Algebraic Attack on Ciphers with Low-Degree Round Functions: Application to Full MiMC","volume":"Volume 12491","author":"Moriai","year":"2020","journal-title":"Advances in Cryptology\u2014ASIACRYPT 2020, Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, Republic of Korea, 7\u201311 December 2020, Proceedings, Part I"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1007\/s10623-022-01136-x","article-title":"On the algebraic degree of iterated power functions","volume":"91","author":"Bouvier","year":"2023","journal-title":"Des. Codes Cryptogr."},{"key":"ref_29","first-page":"241","article-title":"On the Field-Based Division Property: Applications to MiMC, Feistel MiMC and GMiMC","volume":"Volume 13793","author":"Agrawal","year":"2022","journal-title":"Advances in Cryptology\u2014ASIACRYPT 2022, Proceedings of the 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, 5\u20139 December 2022, Proceedings, Part III"},{"key":"ref_30","first-page":"287","article-title":"Coefficient Grouping: Breaking Chaghri and More","volume":"Volume 14007","author":"Hazay","year":"2023","journal-title":"Advances in Cryptology\u2014EUROCRYPT 2023, Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 23\u201327 April 2023, Proceedings, Part IV"},{"key":"ref_31","unstructured":"Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., and Halevi, S. (2016, January 24\u201328). MPC-Friendly Symmetric Key Primitives. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria."},{"key":"ref_32","unstructured":"Lai, X. (1994). Communications and Cryptography: Two Sides of One Tapestry, Springer."},{"key":"ref_33","first-page":"196","article-title":"Truncated and Higher Order Differentials","volume":"Volume 1008","author":"Preneel","year":"1994","journal-title":"Proceedings of the Fast Software Encryption: Second International Workshop, Leuven, Belgium, 14\u201316 December 1994, Proceedings"},{"key":"ref_34","first-page":"28","article-title":"The Interpolation Attack on Block Ciphers","volume":"Volume 1267","author":"Biham","year":"1997","journal-title":"FSE \u201997, Proceedings of the Fast Software Encryption, 4th International Workshop, Haifa, Israel, 20\u201322 January 1997, Proceedings"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"73","DOI":"10.46586\/tosc.v2022.i3.73-101","article-title":"Algebraic Attacks against Some Arithmetization-Oriented Primitives","volume":"2022","author":"Bariant","year":"2022","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref_36","unstructured":"Nagell, T. (1951). Introduction to Number Theory, Wiley."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"von zur Gathen, J., and Gerhard, J. (2013). Modern Computer Algebra, Cambridge University Press. [3rd ed.].","DOI":"10.1017\/CBO9781139856065"},{"key":"ref_38","first-page":"19","article-title":"A theoretical basis for the reduction of polynomials to canonical forms","volume":"10","author":"Buchberger","year":"1976","journal-title":"SIGSAM Bull."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","article-title":"A new efficient algorithm for computing Gr\u00f6bner bases (F4)","volume":"139","author":"Faugere","year":"1999","journal-title":"J. Pure Appl. Algebra"},{"key":"ref_40","unstructured":"Faugere, J.C. (2002, January 7\u201310). A new efficient algorithm for computing Gr\u00f6bner bases without reduction to zero (F 5). Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, Lille, France."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1006\/jsco.1993.1051","article-title":"Efficient Computation of Zero-Dimensional Gr\u00f6bner Bases by Change of Ordering","volume":"16","author":"Gianni","year":"1993","journal-title":"J. Symb. Comput."},{"key":"ref_42","unstructured":"van der Hoeven, J., and van Hoeij, M. (2012). ISSAC\u201912, Proceedings of the International Symposium on Symbolic and Algebraic Computation, Grenoble, France, 22\u201325 July 2012, ACM."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.jsc.2014.09.025","article-title":"On the complexity of the F5 Gr\u00f6bner basis algorithm","volume":"70","author":"Bardet","year":"2015","journal-title":"J. Symb. Comput."},{"key":"ref_44","unstructured":"Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. (2007, January 24\u201325). Sponge functions. Proceedings of the ECRYPT Hash Workshop, Barcelona, Spain."},{"key":"ref_45","first-page":"181","article-title":"On the Indifferentiability of the Sponge Construction","volume":"Volume 4965","author":"Smart","year":"2008","journal-title":"Advances in Cryptology\u2014EUROCRYPT 2008, Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, 13\u201317 April 2008, Proceedings"},{"key":"ref_46","first-page":"83","article-title":"An O(M(n) logn) Algorithm for the Jacobi Symbol","volume":"Volume 6197","author":"Hanrot","year":"2010","journal-title":"Algorithmic Number Theory, Proceedings of the 9th International Symposium, ANTS-IX, Nancy, France, 19\u201323 July 2010, Proceedings"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/15\/8\/1563\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T20:30:26Z","timestamp":1760128226000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/15\/8\/1563"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,10]]},"references-count":46,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2023,8]]}},"alternative-id":["sym15081563"],"URL":"https:\/\/doi.org\/10.3390\/sym15081563","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2023,8,10]]}}}