Grover on Caesar and Vigenère Ciphers

Gyeongju Song; Kyungbae Jang; Hyunji Kim; Wai-Kong Lee; Hwajeong Seo

Paper 2021/554

Grover on Caesar and Vigenère Ciphers

Gyeongju Song, Kyungbae Jang, Hyunji Kim, Wai-Kong Lee, and Hwajeong Seo

Abstract

Quantum computers can solve or accelerate specific problems that were not possible with classical computers. Grover's search algorithm, a representative quantum algorithm, finds a specific solution from $N$ unsorted data with $O(\sqrt{N})$ queries. This quantum algorithm can be used to recover the key of symmetric cryptography. In this paper, we present a practical quantum attack using Grover's search to recover the key of ciphers ({\tt Caesar} and {\tt Vigenère}). The proposed quantum attack is simulated with quantum programming tools (ProjectQ and Qiskit) provided by IBM. Finally, we minimize the use of quantum resources and recover the key with a high probability.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint. MINOR revision.
Keywords: Quantum Computers Grover's Search Algorithm Caesar Cipher Vigenère Cipher
Contact author(s): hwajeong84 @ gmail com
thdrudwn98 @ gmail com
starj1023 @ gmail com
khj1594012 @ gmail com
waikonglee @ gachon ac kr
History: 2021-06-18: last of 2 revisions; 2021-04-27: received; See all versions
Short URL: https://ia.cr/2021/554
License: CC BY

BibTeX

@misc{cryptoeprint:2021/554,
      author = {Gyeongju Song and Kyungbae Jang and Hyunji Kim and Wai-Kong Lee and Hwajeong Seo},
      title = {Grover on Caesar and Vigenère Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2021/554},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/554}},
      url = {https://eprint.iacr.org/2021/554}
}