Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

journal of Groups complexity cryptology

Two-party key establishment: From passive to active security without introducing new assumptions

Kashi Neupane

Published May 1, 2012• 1 citation
Publisher

Abstract

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.

DOI
10.1515/gcc-2012-0005

Related papers

Survey of computational assumptions used in cryptography broken or not by Shor's algorithm

Hong Ping Zhu

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.

•Jan 1, 2001•5 citations

Efficient cryptographic protocols preventing man-in-the-middle attacks

Zvi Galil, Jonathan I. Katz

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.

•Jan 1, 2002•31 citations

Towards Solving Real-world Problems of Post-quantum Cryptography

Suparna Kundu

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.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 19, 2025•0 citations

An Efficient and Secure Protocol for Multi-party Key Establishment

Gwoboa Horng

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.

The Computer Journal•May 1, 2001•22 citations

Classical cryptographic protocols in a quantum world

Sean Hallgren, Adam Smith, Fang Song

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.

arXiv:1507.01625•International Journal of Quantum Information•Jun 1, 2015•15 citations

Post-quantum cryptography: from classical public-key systems to post-quantum secure schemes

MO Wentao, Wei TAO, Zhenhou Hong +5 more

With the development of quantum computing, traditional public-key cryptographic systems based on integer factorization and discrete logarithm problems face security challenges. To systematically review the research progress of post-quantum cryptography, its theoretical foundations, algorithmic systems, engineering implementation, and deployment issues were surveyed. First, the vulnerabilities of traditional cryptographic systems under quantum attack models and the constraints of protocol migration were analyzed. Then, post-quantum cryptographic schemes, including lattice-based, hash-based, code-based, multivariate, and isogeny-based schemes, were classified and compared, and hardware adaptation, implementation optimization, and implementation security were discussed in combination with CPU, FPGA, and embedded platforms. Under a unified testing environment, the performance and communication overhead of traditional, post-quantum, hybrid, and selected signature and KEM schemes proposed and publicly implemented by domestic research teams were evaluated. The results show that different technical routes involve obvious trade-offs among security, computational efficiency, and communication cost. Finally, challenges in long-term security validation, implementation security, system migration, and engineering deployment were summarized, providing a reference for post-quantum cryptography research and application.

•Jan 1, 2026•0 citations
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.
With the development of quantum computing, traditional public-key cryptographic systems based on integer factorization and discrete logarithm problems face security challenges. To systematically review the research progress of post-quantum cryptography, its theoretical foundations, algorithmic systems, engineering implementation, and deployment issues were surveyed. First, the vulnerabilities of traditional cryptographic systems under quantum attack models and the constraints of protocol migration were analyzed. Then, post-quantum cryptographic schemes, including lattice-based, hash-based, code-based, multivariate, and isogeny-based schemes, were classified and compared, and hardware adaptation, implementation optimization, and implementation security were discussed in combination with CPU, FPGA, and embedded platforms. Under a unified testing environment, the performance and communication overhead of traditional, post-quantum, hybrid, and selected signature and KEM schemes proposed and publicly implemented by domestic research teams were evaluated. The results show that different technical routes involve obvious trade-offs among security, computational efficiency, and communication cost. Finally, challenges in long-term security validation, implementation security, system migration, and engineering deployment were summarized, providing a reference for post-quantum cryptography research and application.