In this thesis we present our contribution in the field of post-quantum cryptography. We introduce a new notion of weakly Random-Self-Reducible public-key cryptosystem and show how it can be used to implement secure Oblivious Transfer. We also show that two recent (Post-quantum) cryptosystems can be considered as weakly Random-Self-Reducible. We introduce a new problem called Isometric Lattice Problem and reduce graph isomorphism and linear code equivalence to this problem. We also show that this problem has a perfect zero-knowledge interactive proof with respect to a malicious verifier; this is the only hard problem in lattices that is known to have this property.
In this thesis we present our contribution in the field of post-quantum cryptography. We introduce a new notion of weakly Random-Self-Reducible public-key cryptosystem and show how it can be used to implement secure Oblivious Transfer. We also show that two recent (Post-quantum) cryptosystems can be considered as weakly Random-Self-Reducible. We introduce a new problem called Isometric Lattice Problem and reduce graph isomorphism and linear code equivalence to this problem. We also show that this problem has a perfect zero-knowledge interactive proof with respect to a malicious verifier; this is the only hard problem in lattices that is known to have this property.
Lattice-based hard problems are a leading candidate for implementation in future public key cryptographic schemes due to their conjectured quantum resilience. Lattice-based problems offer certain advantages over non-lattice-based cryptosystems, such as a relatively short key length [3] and versatility, since lattice cryptosystems can offer both encryption schemes (to securely transmit data from sender to receiver) and signature schemes (used for a receiver to verify that information actually originated from the claimed sender) [2]. Notably they are also the only known class of problems which give rise to fully homomorphic encryption schemes, in which computations can be securely performed on encrypted data [1]. Many of the 2017 submissions to the NIST Post-Quantum Cryptography challenge are based on lattice problems [4].
The security of conventional public-key cryptography schemes is based on mathematical problems which are considered to be infeasible to solve by classical computers in a reasonable amount of time. However, the rise of quantum computers might break this security in the future. Post-quantum cryptography (PQC) aims to achieve secure schemes which are resistant against attacks assisted by quantum computers. Public-key cryptography refers to asymmetric cryptography in which encryption is done with a public key and decryption is done with a private key. Characteristic properties of public-key cryptography include the possibility to derive the private key from public information by solving some presumably hard problem. The hardness of the problem constitutes the basis for the system's security. In the post-quantum era, the security must be based on problems that are too hard to solve even for quantum computers. In this thesis, we will study lattice-based cryptography which is believed to serve as a good candidate for secure post-quantum public-key cryptography. Our main attention is in the problem of learning with errors, which is in the base of some lattice-based schemes and is linked to the hard problem of finding short vectors in a lattice.
Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness. In this work, we argue that decoding random quantum stabilizer codes---a quantum analog of the well-studied LPN problem---is an excellent candidate. This task occupies a unique middle ground: it is inherently native to quantum computation, yet admits an equivalent formulation with purely classical input and output, as recently shown by Khesin et al. (STOC '26). We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania, including public-key encryption (PKE) and oblivious transfer (OT), as well as one-way functions. Our constructions are moreover practically efficient: our PKE scheme achieves essentially the same efficiency as state-of-the-art LPN-based PKE. We also provide substantial evidence that stabilizer decoding does not reduce to LPN, suggesting that the former problem constitutes a genuinely new post-quantum assumption. Our primary technical contributions are twofold. First, we give a reduction from random quantum stabilizer decoding to an average-case problem closely resembling LPN, but which is equipped with additional symplectic algebraic structure. While this structure is essential to the quantum nature of the problem, it raises significant barriers to cryptographic security reductions. Second, we develop a new suite of scrambling techniques for such structured linear spaces, and use them to produce rigorous security proofs for all of our constructions.
The security of current public-key cryptosystems relies on the hardness of factoring large integers or solving discrete logarithm problems. However, these mathematical problems can be solved in polynomial time using a quantum computer. This vulnerability has prompted research into post-quantum cryptography using alternative mathematical problems that are secure in the era of quantum computers. In this regard, the National Institute of Standards and Technology (NIST) began to standardize post-quantum cryptography in 2016. In this expository article, we give an overview of recent research on post-quantum cryptography. In particular, we describe the construction and security of multivariate polynomial cryptosystems and lattice-based cryptosystems, which are the main candidates of post-quantum cryptography.
Recent developments in quantum computers pose an imminent threat to cryptography since many widely used cryptographic schemes will no longer be secure. This worrisome scenario motivated a growing interest in the field of post-quantum cryptography, which aims to design cryptosystems that are postquantum secure, i.e. secure against quantum-capable adversaries. While finding post-quantum computational hardness assumptions is pivotal to achieve this goal, an issue that is often overlooked is provable security. In fact, to prove that the post-quantum computational hardness necessarily implies post-quantum security of the derived cryptosystem, the reduction argument that establishes this implication also needs to be post-quantum. As such, many new methods have been devised in the last few years to handle this adaptation to the quantum setting. In particular, the quantum analogue of the Random Oracle Model has garnered special interest, as it is the foundation of many cryptographic schemes, from public-key encryption to digital signatures. It is also very problematic and usually the main culprit of the failure of security proofs when transitioning to the quantum setting. This work offers a comprehensive exposition on the most influential techniques developed in the last decade to enable or facilitate the construction of security proofs in the Quantum Random Oracle Model (QROM). Each presented technique offers an unique purpose and a solution to a problem provoked by the QROM, and, as such, as a whole, this works allows for an understanding of the most common strategies to construct these type of security proofs. This is accomplished by presenting and analyzing the security proof of three cryptographic schemes set in this model, which underlines the central role these techniques take in provable quantum security.
Public-key cryptography is a key technology for making the Internet and other IT infrastructures secure. The security of the established public-key cryptosystems relies on the difficulty of factoring large composite integers or computing discrete logarithms. However, it is unclear whether these computational problems remain intractable in the future. For example, Shor showed in 1994 that quantum computers can be used to factor integers and to compute discrete logarithms in polynomial time. It is therefore necessary to develop alternative public-key cryptosystems which do not rely on the difficulty of factoring or computing discrete logarithms and which are secure even against quantum computer attacks. We call such cryptosystems quantum-immune. To prove the security of these quantum-immune cryptosystems, appropriate security models have to be used. Since quantum computers are able to solve problems in polynomial time which are supposed to be intractable for classical computers, the existing security models are inadequate in the presence of quantum adversaries. Therefore, new security models have to be developed to capture quantum adversaries. Properties of these new security models have to be investigated. On a more practical level, the quantum-immune cryptosystems have to be implemented in a way that they can seamlessly replace established cryptosystems. The implementations have to be efficient and suitable for resource-constrained devices. They must easily integrate into existing public-key infrastructures. This thesis contributes to both the theory and practice of quantum-immune cryptography, addressing the above-mentioned challenges. In the theoretical part, we concentrate on the quantum zero-knowledge property of interactive proof systems. We show for the first time that the quantum statistical, perfect, and computational zero-knowledge properties are preserved under sequential composition of interactive proof systems. In the practical part, we provide implementations of the most important quantum-immune cryptosystems. We present efficiency improvements of some of the alternative cryptosystems. The implementations are very efficient and easily integrate into existing public-key infrastructures. We present comprehensive timings that show that the alternative cryptosystems are competitive or even superior compared to established cryptosystems. Finally, we present a new cryptographic API that is particularly well-suited for resource-constrained devices like mobile phones and PDAs. With this API, the alternative cryptosystems can also be used with these devices.