Paper 2024/894
Quantum Algorithms for Fast Correlation Attacks on LFSR-Based Stream Ciphers
Abstract
This paper presents quantum algorithms for fast correlation attacks, one of the most powerful techniques for cryptanalysis on LFSR-based stream ciphers in the classical setting.
Typical fast correlation attacks recover a value related to the initial state of the underlying LFSR by solving a decoding problem on a binary linear code with the Fast Walsh-Hadamard Transform (FWHT).
Applying the FWHT on a function in the classical setting is mathematically equivalent to applying the Hadamard transform on the corresponding state in quantum computation.
While the classical FWHT on a function with
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- A major revision of an IACR publication in ASIACRYPT 2024
- Keywords
- quantum cryptanalysisfast correlation attackLFSR-based stream cipher
- Contact author(s)
- akinori hosoyamada @ ntt com
- History
- 2024-09-20: revised
- 2024-06-05: received
- See all versions
- Short URL
- https://ia.cr/2024/894
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/894, author = {Akinori Hosoyamada}, title = {Quantum Algorithms for Fast Correlation Attacks on {LFSR}-Based Stream Ciphers}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/894}, year = {2024}, url = {https://eprint.iacr.org/2024/894} }