Abstract. Key establishment protocols based on hardness assumptions, such as the discrete logarithm problem and the integer factorization problem, are vulnerable to quantum computer attacks, whereas the protocols based on other hardness assumptions, such as the conjugacy search problem and the decomposition search problem, can resist such attacks. The existing protocols based on the hardness assumptions which can resist quantum computer attacks are only passively secure. Compilers are used to convert a passively secure protocol to an actively secure protocol. Compilers involve some tools such as a signature scheme and a collision-resistant hash function. If there are only passively secure protocols but not a signature scheme based on the same assumption, then the application of existing compilers requires the use of such tools based on different assumptions. But the introduction of new tools, based on different assumptions, makes the new actively secure protocol rely on more than one hardness assumption. We offer an approach to derive an actively secure two-party protocol from a passively secure two-party protocol without introducing further hardness assumptions. This serves as a useful formal tool to transform any basic algebraic method of public key cryptography to the real world applicable cryptographic scheme.
Abstract. Key establishment protocols based on hardness assumptions, such as the discrete logarithm problem and the integer factorization problem, are vulnerable to quantum computer attacks, whereas the protocols based on other hardness assumptions, such as the conjugacy search problem and the decomposition search problem, can resist such attacks. The existing protocols based on the hardness assumptions which can resist quantum computer attacks are only passively secure. Compilers are used to convert a passively secure protocol to an actively secure protocol. Compilers involve some tools such as a signature scheme and a collision-resistant hash function. If there are only passively secure protocols but not a signature scheme based on the same assumption, then the application of existing compilers requires the use of such tools based on different assumptions. But the introduction of new tools, based on different assumptions, makes the new actively secure protocol rely on more than one hardness assumption. We offer an approach to derive an actively secure two-party protocol from a passively secure two-party protocol without introducing further hardness assumptions. This serves as a useful formal tool to transform any basic algebraic method of public key cryptography to the real world applicable cryptographic scheme.
We survey the computational assumptions of various cryptographic schemes, and discuss the security threat posed by Shor's quantum algorithm. One-way functions form the basis of public-key cryptography. Although we have candidate hard problems that are believed to be one-way, none has been proven to be so. Therefore the security of the corresponding cryptographic schemes depends on the intractability assumptions of these problems. Two major species of such problems, factoring and discrete logarithm, are widely believed to be intractable, and serve as the basis of many popular schemes. However, these two problems turned out to be polynomial-time solvable on a hypothetical quantum computer using Shor's algorithm. This is the most worrisome long-term threat to current public-key cryptosystems. In the thesis we provide a review of existing cryptosystems, with a focus on their underlying computational assumptions and the security. Other than factoring and discrete logarithm, schemes have been proposed based on error-correcting codes, subset-sum and subset-product problems, lattice, polynomials, combinatorial group theory, number fields, etc. Many are to be furtherly evaluated in future research.
In the analysis of many cryptographie protocole, it is useful to distinguish two classes of attacks: passive attacks in which an adversary eavesdrops on messages sent between honest users and active attacks (i.e, “man-in-the-middle” attacks) in which—in addition to eavesdropping—the adversary inserts, deletes, or arbitrarily modifies messages sent from one user to another. Passive attacks are well characterized (the adversary's choices are inherently limited) and techniques for achieving security against passive attacks are relatively well understood. Indeed, cryptographers have long focused on methods for countering passive eavesdropping attacks, and much work in the 1970's and 1980's has dealt with formalizing notions of security and providing provably-secure solutions for this setting. On the other hand, active attacks are not well characterized and precise modeling has been difficult. Few techniques exist for dealing with active attacks, and designing practical protocols secure against such attacks remains a challenge.
This dissertation considers active attacks in a variety of settings and provides new, provably-secure protocols preventing such attacks. Proofs of security are in the standard cryptographie model and rely on well-known cryptographie assumptions. The protocols presented here are efficient and practical, and may find application in real-world systems.
Public-key cryptography is indispensable in maintaining the security and integrity of digital data. The most widely used current public-key cryptography is based on the integer factorization problem and the elliptic-curve discrete logarithm problem, which are vulnerable against an adversary with large-scale quantum computers. Fortunately, post-quantum cryptography (PQC) can provide security against both classical and quantum adversaries. Due to rapid advancement in quantum computer development, the transition from classical public-key cryptography to PQC has become imperative. A watershed moment in this transition is the recent publication of a set of PQC schemes by the National Institute of Standards and Technology (NIST). Although it is a significant step, the research and development in PQC is quite immature compared to several decades-old classical public-key cryptographic schemes. Therefore, several open problems, such as physical attack analysis and their countermeasures, application-specific modifications, lightweight implementations for resource-constrained devices, integration into different secure protocols, etc., need to be addressed before the widespread deployment of PQC in real-world applications. This dissertation aims to address some of these problems in order to bridge the gap between the theory and practice of PQC.
In this paper, a multi-party key establishment protocol based on the difficulty of calculating discrete logarithms in a finite field is proposed with the following features. It requires a constant number (independent of the number of participants) of rounds. All messages have the same constant size. All participants perform a constant number of exponential operations. All participants agree on a key together with two random integers simultaneously. Furthermore, to establish a new key when the set of participants is changed is easy. We also show that this new scheme is secure against passive attacks provided that the Diffie–Hellman key agreement protocol is secure in the sense that the established key is computationally indistinguishable from a random value.
Cryptographic protocols, such as protocols for secure function evaluation (SFE), have played a crucial role in the development of modern cryptography. The extensive theory of these protocols, however, deals almost exclusively with classical attackers. If we accept that quantum information processing is the most realistic model of physically feasible computation, then we must ask: What classical protocols remain secure against quantum attackers? Our main contribution is showing the existence of classical two-party protocols for the secure evaluation of any polynomial-time function under reasonable computational assumptions (for example, it suffices that the learning with errors problem be hard for quantum polynomial time). Our result shows that the basic two-party feasibility picture from classical cryptography remains unchanged in a quantum world.
The landscape of modern cryptography is fundamentally challenged by the advent of quantum computing. Current public-key cryptosystems, which form the bedrock of secure digital communication, rely on the computational hardness of problems such as integer factorization (RSA) and the discrete logarithm problem (ECC). However, Shor's algorithm, if implemented on a sufficiently powerful quantum computer, can efficiently break these schemes, rendering them insecure. This paper explores the critical transition from these classical number theory problems to lattice-based cryptography, presenting a comprehensive analysis of the motivations, theoretical underpinnings, and practical implications for forging post-quantum cryptographic security. We delve into the mathematical foundations of lattice problems, such as the Shortest Vector Problem (SVP) and Learning With Errors (LWE), which are believed to resist known quantum algorithms. Through a thorough literature review, we trace the evolution of cryptographic thought, detailing the vulnerabilities of pre-quantum schemes and the emergence of lattice-based constructions as leading candidates for post-quantum standardization. The methodology outlines a comparative theoretical analysis of security, efficiency, and robustness against both classical and quantum attacks. Results demonstrate the compelling advantages of lattice-based schemes in terms of provable security reductions and resistance to quantum threats, albeit with considerations for increased key and ciphertext sizes. The discussion highlights the challenges and opportunities in the deployment and standardization of these new cryptographic primitives, emphasizing their critical role in securing future digital infrastructures. This work concludes that lattice-based cryptography offers a robust and theoretically sound pathway to establishing enduring security in a quantum-threatened world.