Optimized Linear Cryptanalysis of BAKSHEESH: A Case Study with Partial-Sum, FWT, and Key-Bridging

Abstract

BAKSHEESH is a lightweight block cipher designed to achieve efficient implementation while maintaining adequate security, and is considered a competitor to ciphers such as GIFT. In this paper, we study the linear cryptanalysis of BAKSHEESH in a systematic and optimized manner. First, we develop a mixed-integer linear programming based automatic method to search for linear distinguishers of BAKSHEESH and identify a 21-round linear distinguisher. Then, in the key-recovery phase, for the first time, we propose an optimized strategy that combines the partial-sum, fast Walsh–Hadamard transform, and key-bridging techniques. This combination allows a significant reduction in the time complexity of the attack. Using the 21-round linear distinguisher, we mount a 24-round key-recovery attack on BAKSHEESH, which improves the previously best-known result by three rounds. In addition, we present 21-, 22-, and 23-round key-recovery attacks on BAKSHEESH to provide a detailed comparison, offering a comprehensive evaluation of BAKSHEESH’s security. Through these studies, we provide a deeper understanding of BAKSHEESH’s resistance to linear cryptanalysis and offer a quantitative assessment of its overall security margins.

Keywords

BAKSHEESH / Linear Cryptanalysis / Mixed-Integer Linear Programming / Fast Walsh–Hadamard Transform / Partial-Sum / Key-Bridging / Key-Recovery Attack

RIGHTS & PERMISSIONS

Higher Education Press 2026

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.