{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T07:15:56Z","timestamp":1771658156066,"version":"3.50.1"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2020,8,4]],"date-time":"2020-08-04T00:00:00Z","timestamp":1596499200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61379138"],"award-info":[{"award-number":["61379138"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,4,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Automatic search methods have been widely used for cryptanalysis of block ciphers, especially for the most classic cryptanalysis methods\u2014differential and linear cryptanalysis. However, the automatic search methods, no matter based on MILP, SMT\/SAT or CP techniques, can be inefficient when the search space is too large. In this paper, we propose three new methods to improve Matsui\u2019s branch-and-bound search algorithm, which is known as the first generic algorithm for finding the best differential and linear trails. The three methods, named reconstructing DDT and LAT according to weight, executing linear layer operations in minimal cost and merging two 4-bit S-boxes into one 8-bit S-box, respectively, can efficiently speed up the search process by reducing the search space as much as possible and reducing the cost of executing linear layer operations. We apply our improved algorithm to DESL and GIFT, which are still the hard instances for the automatic search methods. As a result, we find the best differential trails for DESL (up to 14-round) and GIFT-128 (up to 19-round). The best linear trails for DESL (up to 16-round), GIFT-128 (up to 10-round) and GIFT-64 (up to 15-round) are also found. To the best of our knowledge, these security bounds for DESL and GIFT under single-key scenario are given for the first time. Meanwhile, it is the longest exploitable (differential or linear) trails for DESL and GIFT. Furthermore, benefiting from the efficiency of the improved algorithm, we do experiments to demonstrate that the clustering effect of differential trails for 13-round DES and DESL are both weak.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaa090","type":"journal-article","created":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T19:08:47Z","timestamp":1595704127000},"page":"610-627","source":"Crossref","is-referenced-by-count":5,"title":["Improving Matsui\u2019s Search Algorithm For The Best Differential\/Linear Trails And Its Applications For DES, DESL And GIFT"],"prefix":"10.1093","volume":"64","author":[{"given":"Fulei","family":"Ji","sequence":"first","affiliation":[{"name":"State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China"},{"name":"School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wentao","family":"Zhang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China"},{"name":"School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianyou","family":"Ding","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China"},{"name":"School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,8,4]]},"reference":[{"key":"2021041913235079400_ref1","first-page":"2","article-title":"Differential Cryptanalysis of DES-like Cryptosystems","volume-title":"CRYPTO 1990","author":"Biham","year":"1990"},{"key":"2021041913235079400_ref2","first-page":"386","article-title":"Linear Cryptanalysis Method for DES Cipher","volume-title":"EUROCRYPT 1993","author":"Matsui","year":"1993"},{"key":"2021041913235079400_ref3","first-page":"366","article-title":"On Correlation Between the Order of S-Boxes and the Strength of DES","volume-title":"EUROCRYPT 1994","author":"Matsui","year":"1994"},{"key":"2021041913235079400_ref4","first-page":"157","article-title":"Improving the Search Algorithm for the Best Linear Expression","volume-title":"CRYPTO 1995","author":"Ohta","year":"1995"},{"key":"2021041913235079400_ref5","first-page":"41","article-title":"Best Differential Characteristic Search of FEAL. Fast Software Encryption","volume-title":"4th Int. Workshop, FSE \u201997","author":"Aoki","year":"1997"},{"key":"2021041913235079400_ref6","first-page":"259","article-title":"Speeding Up the Search Algorithm for the Best Differential and Best Linear Trails","volume-title":"Information Security and Cryptology\u201410th Int. Conf., Inscrypt 2014","author":"Bao","year":"2014"},{"key":"2021041913235079400_ref7","first-page":"57","article-title":"Differential and Linear Cryptanalysis Using Mixed-Integer Linear Programming","volume-title":"Information Security and Cryptology\u20147th Int. Conf., Inscrypt 2011","author":"Mouha","year":"2011"},{"key":"2021041913235079400_ref8","first-page":"551","article-title":"Security evaluation against differential cryptanalysis for block cipher structures","volume":"2011","author":"Wu","year":"2011","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"2021041913235079400_ref9","first-page":"39","article-title":"Automatic Security Evaluation of Block Ciphers with S-bP Structures Against Related-Key Differential Attacks","volume-title":"Information Security and Cryptology\u20149th Int. Conf., Inscrypt 2013","author":"Sun","year":"2013"},{"key":"2021041913235079400_ref10","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/978-3-662-45611-8_9","article-title":"Automatic Security Evaluation and (Related-Key) Differential Characteristic Search: Application to SIMON, PRESENT, LBlock, DES(L) and Other Bit-Oriented Block Ciphers","volume-title":"ASIACRYPT 2014","author":"Sun","year":"2014"},{"key":"2021041913235079400_ref11","first-page":"97","article-title":"Improvement on the Method for Automatic Differential Analysis and Its Application to Two Lightweight Block Ciphers DESL and LBlock-s","volume-title":"Advances in Information and Computer Security\u201410th Int. Workshop on Security, IWSEC 2015","author":"Sun","year":"2015"},{"key":"2021041913235079400_ref12","first-page":"372","article-title":"MILP-Based Differential Attack on Round-Reduced GIFT","volume-title":"Topics in Cryptology\u2014CT-RSA 2019\u2014The Cryptographers\u2019 Track at the RSA Conference 2019","author":"Zhu","year":"2019"},{"key":"2021041913235079400_ref13","first-page":"49","article-title":"The relationship between the construction and solution of the MILP models and applications","volume":"2019","author":"Li","year":"2019","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"2021041913235079400_ref14","first-page":"35","article-title":"Multiple Differential Cryptanalysis: Theory and Practice","volume-title":"Fast Software Encryption\u201418th Int. Workshop, FSE 2011","author":"Blondeau","year":"2011"},{"key":"2021041913235079400_ref15","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-3-319-26617-6_9","article-title":"Improved Linear Cryptanalysis of Reduced-Round SIMON-32 and SIMON-48","volume-title":"Progress in Cryptology\u2014INDOCRYPT 2015\u201416th Int. Conf. Cryptology in India","author":"Abdelraheem","year":"2015"},{"key":"2021041913235079400_ref16","first-page":"32111:1","article-title":"Automatic search method for multiple differentials and its application on MANTIS","author":"Chen","year":"2019"},{"key":"2021041913235079400_ref17","doi-asserted-by":"crossref","first-page":"265","DOI":"10.46586\/tosc.v2018.i3.265-289","article-title":"Generating Graphs Packed with Paths Estimation of Linear Approximations and Differentials","volume":"2018","author":"Hall-Andersen","year":"2018","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"2021041913235079400_ref18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04722-4","volume-title":"The Design of Rijndael: AES\u2014The Advanced Encryption Standard Information Security and Cryptography","author":"Daemen","year":"2002"},{"key":"2021041913235079400_ref19","first-page":"19","article-title":"Improving the MILP-based security evaluation algorithms against differential cryptanalysis using divide-and-conquer approach","volume":"2019","author":"Zhou","year":"2019","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"2021041913235079400_ref20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-17342-4","article-title":"Information Security and Cryptography","volume-title":"The Block Cipher Companion","author":"Knudsen","year":"2011"},{"key":"2021041913235079400_ref21","first-page":"196","article-title":"New Lightweight DES Variants","volume-title":"Fast Software Encryption, 14th Int. Workshop, FSE 2007","author":"Leander","year":"2007"},{"key":"2021041913235079400_ref22","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/978-3-319-66787-4_16","article-title":"GIFT: A Small Present\u2014Towards Reaching the Limit of Lightweight Encryption","volume-title":"Cryptographic Hardware and Embedded Systems\u2014CHES 2017\u201419th Int. Conf.","author":"Banik","year":"2017"},{"key":"2021041913235079400_ref23","volume-title":"NIST Homepage"},{"key":"2021041913235079400_ref24","first-page":"78","article-title":"Understanding Two-Round Differentials in AES. Security and Cryptography for Networks","volume-title":"5th Int. Conf., SCN 2006","author":"Daemen","year":"2006"},{"key":"2021041913235079400_ref25","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-9314-6","volume-title":"Differential Cryptanalysis of the Data Encryption Standard","author":"Biham","year":"1993"},{"key":"2021041913235079400_ref26","first-page":"1805","article-title":"Milp-based related-key rectangle attack and its application to GIFT, Khudra, MIBS","volume":"62","author":"Chen","year":"2019","journal-title":"Comput. J."},{"key":"2021041913235079400_ref27","doi-asserted-by":"crossref","first-page":"175769","DOI":"10.1109\/ACCESS.2019.2957581","article-title":"Related-key differential cryptanalysis of the reduced-round block cipher GIFT","volume":"7","author":"Cao","year":"2019","journal-title":"IEEE Access"},{"key":"2021041913235079400_ref28","first-page":"555","article-title":"Related-Key Boomerang Attacks on GIFT with Automated Trail Search Including BCT Effect","volume-title":"Information Security and Privacy\u201424th Australasian Conference, ACISP 2019","author":"Liu","year":"2019"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/4\/610\/37161740\/bxaa090.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/4\/610\/37161740\/bxaa090.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T03:19:19Z","timestamp":1618888759000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/4\/610\/5880463"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,4]]},"references-count":28,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2020,8,4]]},"published-print":{"date-parts":[[2021,4,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaa090","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,4]]},"published":{"date-parts":[[2020,8,4]]}}}