{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T23:52:12Z","timestamp":1769039532308,"version":"3.49.0"},"reference-count":71,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2023,4,4]],"date-time":"2023-04-04T00:00:00Z","timestamp":1680566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100005357","name":"Slovak Research and Development Agency","doi-asserted-by":"publisher","award":["APVV-19-0220"],"award-info":[{"award-number":["APVV-19-0220"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>In this work, we survey the existing research in the area of algebraic cryptanalysis based on Multiple Right-Hand Sides (MRHS) equations (MRHS cryptanalysis). MRHS equation is a formal inclusion that contains linear combinations of variables on the left-hand side, and a potential set of values for these combinations on the right-hand side. We describe MRHS equation systems in detail, including the evolution of this representation. Then we provide an overview of the methods that can be used to solve MRHS equation systems. Finally, we explore the use of MRHS equation systems in algebraic cryptanalysis and survey existing experimental results.<\/jats:p>","DOI":"10.3390\/cryptography7020019","type":"journal-article","created":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T01:39:26Z","timestamp":1680658766000},"page":"19","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Algebraic Cryptanalysis with MRHS Equations"],"prefix":"10.3390","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1909-9453","authenticated-orcid":false,"given":"Pavol","family":"Zajac","sequence":"first","affiliation":[{"name":"Department of Computer Science and Mathematics, Faculty of Electrical Engineering and Information Technology, Slovak University of Technology in Bratislava, Ilkovi\u010dova 3, 812 19 Bratislava, Slovakia"}]}],"member":"1968","published-online":{"date-parts":[[2023,4,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1002\/j.1538-7305.1949.tb00928.x","article-title":"Communication theory of secrecy systems","volume":"28","author":"Shannon","year":"1949","journal-title":"Bell Syst. Tech. J."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Bard, G. (2009). Algebraic Cryptanalysis, Springer.","DOI":"10.1007\/978-0-387-88757-9"},{"key":"ref_3","first-page":"107","article-title":"Methods to solve algebraic equations in cryptanalysis","volume":"45","author":"Semaev","year":"2010","journal-title":"Tatra Mt. Math. Publ."},{"key":"ref_4","unstructured":"Faugere, J.C., and Joux, A. (2003). Proceedings of the Advances in Cryptology-CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, CA, USA, 17\u201321 August 2003, Springer."},{"key":"ref_5","unstructured":"Courtois, N., Klimov, A., Patarin, J., and Shamir, A. (2000). Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, 14\u201318 May 2000, Springer."},{"key":"ref_6","unstructured":"Courtois, N.T., and Pieprzyk, J. (2002). Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2002: 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, 1\u20135 December 2002, Springer."},{"key":"ref_7","unstructured":"Courtois, N.T. (2003). Proceedings of the Information Security and Cryptology\u2014ICISC 2002: 5th International Conference, Seoul, South Korea, 28\u201329 November 2002, Springer."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Roy, B., and Meier, W. (2004). Proceedings of the Fast Software Encryption, New Delhi, India, 5\u20137 February 2004, Springer.","DOI":"10.1007\/b98177"},{"key":"ref_9","unstructured":"Courtois, N.T., and Bard, G.V. (2007). Proceedings of the Cryptography and Coding: 11th IMA International Conference, Cirencester, UK, 18\u201320 December 2007, Springer."},{"key":"ref_10","unstructured":"Courtois, N.T. (2023, March 01). Algebraic complexity reduction and cryptanalysis of GOST. Cryptology ePrint Archive, Paper 2011\/626. Available online: https:\/\/eprint.iacr.org\/2011\/626."},{"key":"ref_11","first-page":"1","article-title":"Finding hard instances of the satisfiability problem: A survey","volume":"35","author":"Cook","year":"1997","journal-title":"Satisf. Probl. Theory Appl."},{"key":"ref_12","unstructured":"Massacci, F. (August, January 31). Using Walk-SAT and Rel-SAT for cryptographic key search. Proceedings of the IJCAI, Stockholm, Sweden."},{"key":"ref_13","unstructured":"McDonald, C., Charnes, C., and Pieprzyk, J. (2008). Proceedings of the 4th International Workshop on Boolean Functions: Cryptography and Applications, Paris, France, 3 June 2008, Laboratoire d\u2019Informatique Algorithmique: Fondements et Applications."},{"key":"ref_14","unstructured":"Dwivedi, A.D., Klou\u010dek, M., Morawiecki, P., Nikolic, I., Pieprzyk, J., and W\u00f6jtowicz, S. (2023, March 01). SAT-based Cryptanalysis of Authenticated Ciphers from the CAESAR Competition. Cryptology ePrint Archive, Paper 2016\/1053. Available online: https:\/\/eprint.iacr.org\/2016\/1053."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.36244\/ICJ.2019.4.1","article-title":"SAT Attacks on ARX Ciphers with Automated Equations Generation","volume":"9","author":"Andrzejczak","year":"2019","journal-title":"Infocommunications"},{"key":"ref_16","first-page":"187","article-title":"Using SAT solvers in large scale distributed algebraic attacks against low entropy keys","volume":"64","author":"Hromada","year":"2015","journal-title":"Tatra Mt. Math. Publ."},{"key":"ref_17","unstructured":"Albrecht, M., and Cid, C. (2009). Proceedings of the International Workshop on Fast Software Encryption, Leuven, Belgium, 22\u201325 February 2009, Springer."},{"key":"ref_18","unstructured":"Faug\u00e8re, J.C., Perret, L., and Spaenlehauer, P.J. (, January 7\u20139). Algebraic-differential cryptanalysis of DES. Proceedings of the Western European Workshop on Research in Cryptology-WEWoRC, Graz, Austria."},{"key":"ref_19","unstructured":"Wang, M., Sun, Y., Mouha, N., and Preneel, B. (2011). Proceedings of the Australasian Conference on Information Security and Privacy, Melbourne, VI, Australia, 11\u201313 July 2011, Springer."},{"key":"ref_20","first-page":"33","article-title":"A new representation of S-boxes for algebraic differential cryptanalysis","volume":"25","author":"Zajac","year":"2021","journal-title":"Rad Hrvat. Akad. Znan. Umjet. Mat. Znan."},{"key":"ref_21","unstructured":"Renauld, M., and Standaert, F.X. (2010). Proceedings of the Information Security and Cryptology: 5th International Conference, Inscrypt 2009, Beijing, China, 12\u201315 December 2009, Springer."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s13389-012-0028-0","article-title":"Analysis of the algebraic side channel attack","volume":"2","author":"Carlet","year":"2012","journal-title":"J. Cryptogr. Eng."},{"key":"ref_23","unstructured":"Oren, Y., Kirschbaum, M., Popp, T., and Wool, A. (2010). Proceedings of the Cryptographic Hardware and Embedded Systems, CHES 2010: 12th International Workshop, Santa Barbara, CA, USA, 17\u201320 August 2010, Springer."},{"key":"ref_24","unstructured":"Raddum, H. (2007). Proceedings of the Selected Areas in Cryptography: 14th International Workshop, SAC 2007, Ottawa, ON, Canada, 16\u201317 August 2007, Springer."},{"key":"ref_25","first-page":"205","article-title":"MRHS equation systems that can be solved in polynomial time","volume":"67","author":"Zajac","year":"2016","journal-title":"Tatra Mt. Math. Publ."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"349","DOI":"10.4149\/cai_2018_2_349","article-title":"Using Local Reduction for the Experimental Evaluation of the Cipher Security","volume":"37","author":"Zajac","year":"2018","journal-title":"Comput. Inform."},{"key":"ref_27","unstructured":"Zakrevskij, A., and Vasilkova, I. (2000, January 20\u201322). Reducing large systems of Boolean equations. Proceedings of the 4th Internationl Workshop on Boolean Problems, San Jose, CA, USA."},{"key":"ref_28","unstructured":"Raddum, H., and Semaev, I. (2023, March 01). New Technique for Solving Sparse Equation Systems. Cryptology ePrint Archive, Paper 2006\/475. Available online: https:\/\/eprint.iacr.org\/2006\/475."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1137\/070700371","article-title":"Sparse algebraic equations over finite fields","volume":"39","author":"Semaev","year":"2009","journal-title":"SIAM J. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s10623-008-9180-z","article-title":"Solving multiple right hand sides linear equations","volume":"49","author":"Raddum","year":"2008","journal-title":"Des. Codes Cryptogr."},{"key":"ref_31","first-page":"163","article-title":"Connecting the Complexity of MQ-and Code-Based Cryptosystems","volume":"70","author":"Zajac","year":"2017","journal-title":"Tatra Mt. Math. Publ."},{"key":"ref_32","unstructured":"Schilling, T.E., and Raddum, H. (2012). Proceedings of the Information Security and Cryptology-ICISC 2011: 14th International Conference, Seoul, South Korea, 30 November\u20132 December 2011, Springer."},{"key":"ref_33","unstructured":"Schilling, T.E., and Raddum, H. (2012). Proceedings of the International Conference on Sequences and Their Applications, Waterloo, ON, Canada, 4\u20138 June 2012, Springer."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1515\/jmc-2017-0005","article-title":"MRHS solver based on linear algebra and exhaustive search","volume":"12","author":"Raddum","year":"2018","journal-title":"J. Math. Cryptol."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s10623-010-9465-x","article-title":"Sparse Boolean equations and circuit lattices","volume":"59","author":"Semaev","year":"2011","journal-title":"Des. Codes Cryptogr."},{"key":"ref_36","unstructured":"Geiselmann, W., Matheis, K., and Steinwandt, R. (2010). Transactions on Computational Science X, Springer."},{"key":"ref_37","first-page":"93","article-title":"Phase transition in a system of random sparse Boolean equations","volume":"45","author":"Schilling","year":"2010","journal-title":"Tatra Mt. Math. Publ."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","article-title":"A computing procedure for quantification theory","volume":"7","author":"Davis","year":"1960","journal-title":"J. ACM (JACM)"},{"key":"ref_39","unstructured":"Schilling, T.E., and Raddum, H. (2010). Proceedings of the International Workshop on the Arithmetic of Finite Fields, Istanbul, Turkey, 27\u201330 June 2010, Springer."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s11786-013-0163-8","article-title":"Improved agreeing-gluing algorithm","volume":"7","author":"Semaev","year":"2013","journal-title":"Math. Comput. Sci."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.endm.2015.06.006","article-title":"An application of Combinatorics in Cryptography","volume":"49","author":"Horak","year":"2015","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/s10623-015-0058-6","article-title":"MaxMinMax problem and sparse equations over finite fields","volume":"79","author":"Semaev","year":"2016","journal-title":"Des. Codes Cryptogr."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s10623-016-0294-4","article-title":"A combinatorial problem related to sparse systems of equations","volume":"85","author":"Horak","year":"2017","journal-title":"Des. Codes Cryptogr."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1515\/jmc-2013-5012","article-title":"A new method to solve MRHS equation systems and its connection to group factorization","volume":"7","author":"Zajac","year":"2013","journal-title":"J. Math. Cryptol."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s10623-016-0256-x","article-title":"Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity","volume":"82","author":"Zajac","year":"2017","journal-title":"Des. Codes Cryptogr."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"683","DOI":"10.5486\/PMD.2022.Suppl.8","article-title":"On solving sparse MRHS equations with bit-flipping","volume":"100","author":"Zajac","year":"2022","journal-title":"Publ. Math. Debrecen"},{"key":"ref_47","unstructured":"Smi\u010d\u00edk, M., and Zajac, P. (2022). Proceedings of Central European Conference on Cryptology\u2014CECC\u201922, Smolenice, Slovakia, 26\u201329 June 2022, Mathematical Institute, Slovak Academy of Sciences."},{"key":"ref_48","first-page":"38","article-title":"Improving search of solutions of MRHS systems using the Genetic Algorithm","volume":"17","year":"2023","journal-title":"Rev. Cuba. Cienc. Inform."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"23","DOI":"10.36244\/ICJ.2019.4.4","article-title":"A New Type of Signature Scheme Derived from a MRHS Representation of a Symmetric Cipher","volume":"11","author":"Zajac","year":"2019","journal-title":"Infocommunications J."},{"key":"ref_50","unstructured":"Biryukov, A., and De Canni\u00e8re, C. (2011). Encyclopedia of Cryptography and Security, Springer."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s10998-012-6376-9","article-title":"Local reduction and the algebraic cryptanalysis of the block cipher GOST","volume":"65","author":"Zajac","year":"2012","journal-title":"Period. Math. Hung."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1080\/01611194.2011.632807","article-title":"Security evaluation of GOST 28147-89 in view of international standardisation","volume":"36","author":"Courtois","year":"2012","journal-title":"Cryptologia"},{"key":"ref_53","unstructured":"Wu, H. (2023, March 01). The hash function JH. Submission to NIST (Round 3). Available online: https:\/\/www3.ntu.edu.sg\/home\/wuhj\/research\/jh\/jh_round3.pdf."},{"key":"ref_54","unstructured":"Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. Keccak. Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 26\u201330 May 2013."},{"key":"ref_55","first-page":"1","article-title":"A comparison of local reduction and SAT-solver based algebraic cryptanalysis of JH and Keccak","volume":"53","author":"Loderer","year":"2012","journal-title":"Tatra Mt. Math. Publ."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"359","DOI":"10.3233\/FI-2012-635","article-title":"Solving Trivium-based Boolean Equations Using the Method of Syllogisms","volume":"114","author":"Zajac","year":"2012","journal-title":"Fundam. Informaticae"},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"De Canniere, C., and Preneel, B. (2008). Trivium. New Stream Cipher Designs: The eSTREAM Finalists, Springer.","DOI":"10.1007\/978-3-540-68351-3_18"},{"key":"ref_58","first-page":"201","article-title":"Algebraic cryptanalysis of Present based on the method of syllogisms","volume":"53","year":"2012","journal-title":"Tatra Mt. Math. Publ."},{"key":"ref_59","unstructured":"Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J., Seurin, Y., and Vikkelsoe, C. (2007). Proceedings of the Cryptographic Hardware and Embedded Systems-CHES 2007: 9th International Workshop, Vienna, Austria, 10\u201313 September 2007, Springer."},{"key":"ref_60","unstructured":"Poschmann, A., Leander, G., Schramm, K., and Paar, C. (2006, January 12\u201314). A family of light-weight block ciphers based on DES suited for RFID applications. Proceedings of the Workshop on RFID Security\u2013RFIDSec, Graz, Austria."},{"key":"ref_61","doi-asserted-by":"crossref","unstructured":"Matheis, K., Steinwandt, R., and Su\u00e1rez Corona, A. (2019). Algebraic Properties of the Block Cipher DESL. Symmetry, 11.","DOI":"10.3390\/sym11111411"},{"key":"ref_62","unstructured":"Raddum, H., and Kazymyrov, O. (2014). Proceedings of the International Conference on Cryptography and Information Security in the Balkans, Istanbul, Turkey, 16\u201317 October 2014, Springer."},{"key":"ref_63","doi-asserted-by":"crossref","unstructured":"Daemen, J., and Rijmen, V. (2002). The Design of Rijndael, Springer.","DOI":"10.1007\/978-3-662-04722-4"},{"key":"ref_64","unstructured":"Indr\u00f8y, J.P. (2018). Algebraic Attack on Small Scale Variants of AES using Compressed Right Hand Sides. [Master\u2019s Thesis, The University of Bergen]."},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/s12095-018-0304-7","article-title":"Factorization using binary decision diagrams","volume":"11","author":"Raddum","year":"2019","journal-title":"Cryptogr. Commun."},{"key":"ref_66","unstructured":"Indr\u00f8y, J.P., Costes, N., and Raddum, H. (2020). Proceedings of the International Conference on Selected Areas in Cryptography, Kingston, ON, Canada, 11\u201312 August 2020, Springer."},{"key":"ref_67","unstructured":"Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., and Zohner, M. (2015). Proceedings of the Advances in Cryptology\u2013EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 26\u201330 April 2015, Springer."},{"key":"ref_68","unstructured":"Grassi, L., Kales, D., Rechberger, C., and Schofnegger, M. (2023, March 01). Survey of Key-Recovery Attacks on LowMC in a Single Plaintext\/Ciphertext Scenario. Available online: https:\/\/raw.githubusercontent.com\/lowmcchallenge\/lowmcchallenge-material\/master\/docs\/survey.pdf."},{"key":"ref_69","first-page":"7","article-title":"Ascon v1. 2","volume":"5","author":"Dobraunig","year":"2016","journal-title":"Submiss. CAESAR Compet."},{"key":"ref_70","unstructured":"Semaev, I. (2023, March 01). New results in the linear cryptanalysis of DES. Cryptology ePrint Archive, Paper 2014\/361. Available online: https:\/\/eprint.iacr.org\/2014\/361."},{"key":"ref_71","doi-asserted-by":"crossref","first-page":"79","DOI":"10.46586\/tosc.v2018.i2.79-110","article-title":"Separable statistics and multidimensional linear cryptanalysis","volume":"2","author":"Fauskanger","year":"2018","journal-title":"IACR Trans. Symmetric Cryptol."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/2\/19\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:09:46Z","timestamp":1760123386000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/2\/19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,4]]},"references-count":71,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,6]]}},"alternative-id":["cryptography7020019"],"URL":"https:\/\/doi.org\/10.3390\/cryptography7020019","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,4]]}}}