Tools and Attacks in Post-Quantum Cryptography
Open AccessAdvances in quantum computing and the possibility that it could be used to solve problems that have historically been considered to be intractable for classical computers pose a threat to the security of modern-day widespread digital information and communication. This possibility was first demonstrated by Peter Shor with efficient quantum computer algorithms that solve certain computational problems that underlie the security of numerous cryptographic applications, namely the Discrete Logarithm and Integer Factorization problems. For security, the existing infrastructure of cryptographic algorithms and protocols that protect digital information and communication requires these problems to be hard. Decades of research and cryptanalysis seem to indicate that Discrete Logarithm and Integer Factorization are indeed intractable, at least for classical computers. However, this is not the case for quantum computers, evidenced by Shor's algorithms. Even if cryptanalytically relevant quantum computers that are capable of running Shor's algorithms are unlikely to be realized anytime soon, the threat is still real due to at least the following reasons. New cryptosystems have to go through a long process of intense analysis and scrutiny from the conceptual designs to real-world deployment for reliability and security. Moreover, the adversarial strategy known as "store now, decrypt later" makes encrypted data today vulnerable to future quantum computers. This concern motivates an ongoing effort from academia, government, and industry, in researching, standardizing, and adopting post-quantum cryptography, i.e. cryptography that is resistant to the power of quantum computers. In particular, the National Institute of Standards and Technology has initiated a process to solicit, evaluate, and standardize post-quantum public-key algorithms since 2016. There were 69 candidates in the first round of evaluation. During the next several years, these candidate proposals for post-quantum algorithms were subject to public review and cryptanalysis, essentially competing to survive and ultimately become the standards for post-quantum cryptography. At the time of this writing, the fourth round of evaluation is underway. One key-encapsulation mechanism and three digital signature schemes have been announced to be standardized. Four key-encapsulation mechanisms remain in the fourth round for further evaluation. To better understand security, risks, and other related issues in the theory, designs, implementations, and deployment of post-quantum cryptography, in this thesis, I study the following topics.1. The National Institute of Standards and Technology has made clear through its evaluation criteria that cryptographic schemes and their implementations should be resistant to side-channel attacks. Whereas cryptanalysis studies the computational complexity of solving problems related to cryptographic algorithms, side-channel attacks exploit physical characteristics of physical hardware that is used to implement a cryptosystem in the real world. In the first part of my work, I study and demonstrate the feasibility of a class of side-channel attacks on post-quantum schemes submitted to the aforementioned standardization process, by exploiting a physical phenomenon in dynamic random-access memory known as Rowhammer that allows for cross-domain bit flips.2. In addition to studying security issues related to physical implementation and deployment of post-quantum cryptosystems, in the second part of my work, I study some abstract theoretical components that are fundamental to an area within cryptography--isogeny-based cryptography. Isogenies are structure-preserving maps between elliptic curves. As such, isogenies are essential in many different areas of elliptic-curve cryptography, which encompasses post-quantum isogeny-based cryptography. In particular, I explore different ways one can write down explicit expressions, i.e. formulae, for isogenies and therefore compute them on various alternative models of elliptic curves. Having a broader range of different ways to express and compute isogenies could help us better understand the structure of isogenies and their applications.
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.