Improved Quantum Linear Attacks and Application to CAST
This paper studies quantum linear key-recovery attacks on block ciphers. The first such attacks were last-rounds attacks proposed by Kaplan et al. (ToSC 2016), which combine a linear distinguisher with a guess of a partial key. However, the most efficient classical attacks use the framework propose...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2025-06-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://ojs.ub.rub.de/index.php/ToSC/article/view/12246 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850210704138698752 |
|---|---|
| author | Kaveh Bashiri Xavier Bonnetain Akinori Hosoyamada Nathalie Lang André Schrottenloher |
| author_facet | Kaveh Bashiri Xavier Bonnetain Akinori Hosoyamada Nathalie Lang André Schrottenloher |
| author_sort | Kaveh Bashiri |
| collection | DOAJ |
| description |
This paper studies quantum linear key-recovery attacks on block ciphers. The first such attacks were last-rounds attacks proposed by Kaplan et al. (ToSC 2016), which combine a linear distinguisher with a guess of a partial key. However, the most efficient classical attacks use the framework proposed by Collard et al. (ICISC 2007), which computes experimental correlations using the Fast Walsh-Hadamard Transform. Recently, Schrottenloher (CRYPTO 2023) proposed a quantum version of this technique, in which one uses the available data to create a quantum correlation state, which is a superposition of subkey candidates where the amplitudes are the corresponding correlations. A limitation is that the good subkey is not marked in this state, and cannot be found easily.
In this paper, we combine the correlation state with another distinguisher. From here, we can use Amplitude Amplification to recover the right key. We apply this idea to Feistel ciphers and exemplify different attack strategies on LOKI91 before applying our idea on the CAST-128 and CAST-256 ciphers. We demonstrate the approach with two kinds of distinguishers, quantum distinguishers based on Simon’s algorithm and linear distinguishers. The resulting attacks outperform the previous Grover-meet-Simon attacks.
|
| format | Article |
| id | doaj-art-10426b595c3b45ae8bd34c7c49149d6a |
| institution | OA Journals |
| issn | 2519-173X |
| language | English |
| publishDate | 2025-06-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj-art-10426b595c3b45ae8bd34c7c49149d6a2025-08-20T02:09:44ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2025-06-012025210.46586/tosc.v2025.i2.124-165Improved Quantum Linear Attacks and Application to CASTKaveh Bashiri0Xavier Bonnetain1Akinori Hosoyamada2Nathalie Lang3André Schrottenloher4Bundesamt für Sicherheit in der Informationstechnik (BSI), Bonn, GermanyUniversité de Lorraine, CNRS, Inria, LORIA, Nancy, FranceNTT Social Informatics Laboratories, Tokyo, Japan; NTT Research Center for Theoretical Quantum Information, Atsugi, JapanBauhaus-Universität Weimar, Weimar, GermanyUniv Rennes, Inria, CNRS, IRISA, Rennes, France This paper studies quantum linear key-recovery attacks on block ciphers. The first such attacks were last-rounds attacks proposed by Kaplan et al. (ToSC 2016), which combine a linear distinguisher with a guess of a partial key. However, the most efficient classical attacks use the framework proposed by Collard et al. (ICISC 2007), which computes experimental correlations using the Fast Walsh-Hadamard Transform. Recently, Schrottenloher (CRYPTO 2023) proposed a quantum version of this technique, in which one uses the available data to create a quantum correlation state, which is a superposition of subkey candidates where the amplitudes are the corresponding correlations. A limitation is that the good subkey is not marked in this state, and cannot be found easily. In this paper, we combine the correlation state with another distinguisher. From here, we can use Amplitude Amplification to recover the right key. We apply this idea to Feistel ciphers and exemplify different attack strategies on LOKI91 before applying our idea on the CAST-128 and CAST-256 ciphers. We demonstrate the approach with two kinds of distinguishers, quantum distinguishers based on Simon’s algorithm and linear distinguishers. The resulting attacks outperform the previous Grover-meet-Simon attacks. https://ojs.ub.rub.de/index.php/ToSC/article/view/12246Quantum cryptanalysisLinear cryptanalysisFast Fourier TransformCAST |
| spellingShingle | Kaveh Bashiri Xavier Bonnetain Akinori Hosoyamada Nathalie Lang André Schrottenloher Improved Quantum Linear Attacks and Application to CAST IACR Transactions on Symmetric Cryptology Quantum cryptanalysis Linear cryptanalysis Fast Fourier Transform CAST |
| title | Improved Quantum Linear Attacks and Application to CAST |
| title_full | Improved Quantum Linear Attacks and Application to CAST |
| title_fullStr | Improved Quantum Linear Attacks and Application to CAST |
| title_full_unstemmed | Improved Quantum Linear Attacks and Application to CAST |
| title_short | Improved Quantum Linear Attacks and Application to CAST |
| title_sort | improved quantum linear attacks and application to cast |
| topic | Quantum cryptanalysis Linear cryptanalysis Fast Fourier Transform CAST |
| url | https://ojs.ub.rub.de/index.php/ToSC/article/view/12246 |
| work_keys_str_mv | AT kavehbashiri improvedquantumlinearattacksandapplicationtocast AT xavierbonnetain improvedquantumlinearattacksandapplicationtocast AT akinorihosoyamada improvedquantumlinearattacksandapplicationtocast AT nathalielang improvedquantumlinearattacksandapplicationtocast AT andreschrottenloher improvedquantumlinearattacksandapplicationtocast |