Skip to content

Cryptanalysis

Computation and communication are secured by cryptography. For example, a user's data can be made private, along with messages that they send or receive, from malicious agents who interfere to try to learn the sensitive information. A set of algorithms collectively called a cryptosystem endows the security. The attempt to break security is known as cryptanalysis, which has its own set of algorithms. Historically, both cryptography and cryptanalysis considered classical, polynomial-time algorithms as the only realistic ones. The advent of quantum computation forces us to consider attacks via quantum algorithms. Generally, we want to know what is the best algorithm for cryptanalysis, in order to understand the effect on the cryptosystem in the worst case. The effect of quantum attacks can be to void the security of a set of widely used cryptosystems (section on breaking cryptosystems). More broadly, quantum cryptanalysis can reduce a cryptosystem's security (section on weakening cryptosystems), such that it becomes more expensive to implement in a secure manner. While the properties of quantum mechanics can also be used to devise more secure cryptosystems (e.g., quantum key distribution) [1, 2, 3], we consider this area of cryptography to be outside the scope of the present discussion on quantum algorithms.

Bibliography

  1. Charles H. Bennett and Gilles Brassard. Quantum cryptography: public key distribution and coin tossing. Theoretical Computer Science, 560:7–11, 2014. arXiv: https://arxiv.org/abs/2003.06557. URL: https://www.sciencedirect.com/science/article/pii/S0304397514004241, doi:10.1016/j.tcs.2014.05.025.

  2. S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. Shamsul Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden. Advances in quantum cryptography. Adv. Opt. Photon., 12(4):1012–1236, 12 2020. arXiv: https://arxiv.org/abs/1906.01645. URL: https://opg.optica.org/aop/abstract.cfm?URI=aop-12-4-1012, doi:10.1364/AOP.361502.

  3. Feihu Xu, Xiongfeng Ma, Qiang Zhang, Hoi-Kwong Lo, and Jian-Wei Pan. Secure quantum key distribution with realistic devices. Reviews of Modern Physics, 92:025002, 5 2020. arXiv: https://arxiv.org/abs/1903.09051. URL: https://link.aps.org/doi/10.1103/RevModPhys.92.025002, doi:10.1103/RevModPhys.92.025002.