On iterated punctured Grover

Cezary Pilaszewicz; Marian Margraf

Paper 2023/1114

On iterated punctured Grover

Cezary Pilaszewicz

, Freie Universität Berlin

Marian Margraf, Freie Universität Berlin

Abstract

Grover’s algorithm is a very versatile cryptanalytical tool. Even though it doesn’t provide an exponential speed-up, it still changed the cryptographic requirements all over the world. Usually, Grover’s algorithm is executed with a fixed well-defined function indicating good states. In this paper, we want to investigate what happens if the function is changed over time to mark less and less good states. We compute the amplitudes after $2^{s/2}$ steps of an adjusted Grover’s algorithm proposed by Zheng et al. in Nested Quantum Search Model on Symmetric Ciphers and Its Applications (2023). We use the amplitudes to reason that such an approach always leads to a worse run-time when compared to the naïve version. We also indicate at which point in Zheng et al. the counterintuitive nature of quantum computation leads to false assumptions.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Grover’s algorithm quantum computation cryptanalysis
Contact author(s): cezary pilaszewicz @ fu-berlin de
marian margraf @ fu-berlin de
History: 2024-03-18: revised; 2023-07-17: received; See all versions
Short URL: https://ia.cr/2023/1114
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1114,
      author = {Cezary Pilaszewicz and Marian Margraf},
      title = {On iterated punctured Grover},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1114},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1114}
}