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

An Improved Key Agreement Protocol on Braid Groups

Tang Xue

Published Jan 1, 2006• 0 citations
OpenAlex

Abstract

Shor,Boneh,Liptonon et al. present some remarkable quantum algorithms which can solve integer factoring problem, discrete logarithm problem and discrete logarithm problem on elliptic curves in quantum polynomial time. These quantum algorithms are great challenges to classical public key cryptographies based on the above-described hard problems. It seems that braid group is a kind of considerable public key cryptography platform, but current key agreement protocols, such as AAG,AAFG and BDH, all have different degrees of security weaknesses.This paper takes advantage of random braids and non-conjugate transformations to present an improved braid key agreement protocol related to AAG and AAFG, which can make the two communication parties securely share a common key over any insecure channel. This protocol can resists current length-based attacks, linear representation attacks and other conjugacy search attacks.

Related papers

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

Kashi Neupane

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.

journal of Groups complexity cryptology•May 1, 2012•1 citation

An Authenticated Key Agreement Protocol Using Artins Braid Group

Atul Chaturvedi, Dept. of Mathematics, PSIT, Kanpur, India, Dept. of Computer Science, PSIT, Kanpur, India +5 more

This paper proposes a new and efficient key agreement protocol where trusted third party (TTP) is involved. There are various available schemes which are based on number theoretic, elliptic curves etc. Due to the availability of modern computers, these schemes are vulnerable to man in the middle attack (MITM). So there is a requirement of new technique for key agreement which surprises the intruders and enhances the security of communication system. Our proposed protocol utilizes the property of a non commutative group. We have given the security proof of our protocol keeping the fact in mind that decomposition and conjugacy search problem are hard in a group which is non commutative.

International Journal of Computer Sciences and Engineering•Dec 31, 2017•1 citation

A Comparison of Security and its Performance for Key Agreements in Post-Quantum Cryptography

Fábio Borges, Paulo Ricardo Reis, Diogo Augusto Barros Pereira

Nowadays, we are surrounded by devices collecting and transmitting private information. Currently, the two main mathematical problems that guarantee security on the Internet are the Integer Factorization Problem and the Discrete Logarithm Problem. However, Shor's quantum algorithm can easily solve both problems. Therefore, research into cryptographic algorithms that run in classical computers and are resistant to quantum computers is extremely necessary. This area is known as post-quantum cryptography and usually studies asymmetric cryptography. By means of asymptotic analysis, the purpose of this paper is to provide an evaluation of security and its performance for the types of cryptographic systems considered safe against quantum attacks in the second-round NIST Post-Quantum Standardization Process, namely isogeny cryptosystems based on supersingular elliptic curves, error correction code-based encryption system, and lattice-based ring learning with errors. We performed a security comparison of Key Agreements protocols based on these three post-quantum cryptographic primitives and compared them with Discrete Logarithm Problem and Integer Factorization Problem. The comparison of security and its performance is presented by security level, the former by complexity analyses to achieve theoretical minimum key sizes, and the latter by simulation to assess a practical performance comparison. In the complexity analysis, as we increase the security level and then the size of the cryptographic keys increases, techniques based on isogeny outperform all other post-quantum algorithms in relation to key sizes at practical security level. In the performance comparison, the results show that the code-based protocol presents the best results among the others.

IEEE Access•Jan 1, 2020•81 citations

Convertible Authenticated Encryption Scheme over Braid Group

Wei Yun

The rapid development of quantum computing brings great challenges to public key cryptosystems.The braid group,which is non-commutative,provides a new platform of constructing cryptographic protocols.A convertible authenticated encryption scheme over braid group is proposed on the difficulty of conjugacy search problem and multiple conjugacy problem,in which only the designated receiver can recover and authenticate the message,when the sender repudiates the signature,the receiver can prove the dishonesty of the sender by converting the signature to an ordinary one without the cooperating of the sender.As for the resistance against quantum attacks,the proposed scheme has advantage over the schemes based on commutative algebraic structures.

Jisuanji gongcheng•Jan 1, 2011•0 citations

Proxy blind signature scheme based on braid group

Xiufeng Zhao

Three types of traditional hard problem could be resolved by Shor,Boneh and Lipton's quantum algorithms in po-lynomial time.By the braid group constructed a lot of mathematics difficulties were not an effective solution under the conditions of the quantum computer.It seemed that braid group was a kind of considerable considerable cryptography platform in the future.This paper proposed a new proxy blind signature scheme based on conjugate search problem and the p-th root finding problem,and the exchangeable of the group operation between the elements in the left subgroup and the right subgroup of a braid group.Through program analysis shows that the new scheme is effective and feasible.

Jisuanji yingyong yanjiu•Jan 1, 2010•1 citation

New Quantum-Safe Versions of Decisional Diffie-Hellman Assumption in the General Linear Group and Their Applications: Two New Key-agreements

Abdelhaliem Babiker

Diffie-Hellman key-agreement and RSA cryptosystem are widely used to provide security in internet protocols. But both of the two algorithms are totally breakable using Shor's algorithms. This paper proposes two connected matrix-based key-agreements: (a) Diffie-Hellman Key-Agreement with Errors and (b) RSA-Resemble Key-agreement, which, respectively, bear resemblance to Diffie-Hellman key-agreement and RSA cryptosystem and thereby they gain some of the well-known security characteristics of these two algorithms, but without being subject to Shor's algorithms attacks. That is, the new schemes avoid the direct reliance on the hardness of Discrete Logarithm and Integer Factoring problems which are solvable by Shor's algorithms. The paper introduces a new family of quantum-safe hardness assumptions which consist of taking noisy powers of binary matrices. The new assumptions are derived from Decisional Diffie-Hellman (DDH) assumption in the general linear group GL(n,2) by introducing random noise into a quadruple similar to that which define the DDH assumption in GL(n,2(. Thereby we make certain that the resulting quadruple is secure against Shor's algorithm attack and any other DLP-based attack. Thence, the resulting assumptions, are used as basis for the two key-agreement schemes. We prove that these key-agreements are secure -- in key indistinguishability notion -- under the new assumptions.

arXiv:2104.04637•Apr 9, 2021•0 citations
Shor,Boneh,Liptonon et al. present some remarkable quantum algorithms which can solve integer factoring problem, discrete logarithm problem and discrete logarithm problem on elliptic curves in quantum polynomial time. These quantum algorithms are great challenges to classical public key cryptographies based on the above-described hard problems. It seems that braid group is a kind of considerable public key cryptography platform, but current key agreement protocols, such as AAG,AAFG and BDH, all have different degrees of security weaknesses.This paper takes advantage of random braids and non-conjugate transformations to present an improved braid key agreement protocol related to AAG and AAFG, which can make the two communication parties securely share a common key over any insecure channel. This protocol can resists current length-based attacks, linear representation attacks and other conjugacy search attacks.
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.
This paper proposes a new and efficient key agreement protocol where trusted third party (TTP) is involved. There are various available schemes which are based on number theoretic, elliptic curves etc. Due to the availability of modern computers, these schemes are vulnerable to man in the middle attack (MITM). So there is a requirement of new technique for key agreement which surprises the intruders and enhances the security of communication system. Our proposed protocol utilizes the property of a non commutative group. We have given the security proof of our protocol keeping the fact in mind that decomposition and conjugacy search problem are hard in a group which is non commutative.
Nowadays, we are surrounded by devices collecting and transmitting private information. Currently, the two main mathematical problems that guarantee security on the Internet are the Integer Factorization Problem and the Discrete Logarithm Problem. However, Shor's quantum algorithm can easily solve both problems. Therefore, research into cryptographic algorithms that run in classical computers and are resistant to quantum computers is extremely necessary. This area is known as post-quantum cryptography and usually studies asymmetric cryptography. By means of asymptotic analysis, the purpose of this paper is to provide an evaluation of security and its performance for the types of cryptographic systems considered safe against quantum attacks in the second-round NIST Post-Quantum Standardization Process, namely isogeny cryptosystems based on supersingular elliptic curves, error correction code-based encryption system, and lattice-based ring learning with errors. We performed a security comparison of Key Agreements protocols based on these three post-quantum cryptographic primitives and compared them with Discrete Logarithm Problem and Integer Factorization Problem. The comparison of security and its performance is presented by security level, the former by complexity analyses to achieve theoretical minimum key sizes, and the latter by simulation to assess a practical performance comparison. In the complexity analysis, as we increase the security level and then the size of the cryptographic keys increases, techniques based on isogeny outperform all other post-quantum algorithms in relation to key sizes at practical security level. In the performance comparison, the results show that the code-based protocol presents the best results among the others.
The rapid development of quantum computing brings great challenges to public key cryptosystems.The braid group,which is non-commutative,provides a new platform of constructing cryptographic protocols.A convertible authenticated encryption scheme over braid group is proposed on the difficulty of conjugacy search problem and multiple conjugacy problem,in which only the designated receiver can recover and authenticate the message,when the sender repudiates the signature,the receiver can prove the dishonesty of the sender by converting the signature to an ordinary one without the cooperating of the sender.As for the resistance against quantum attacks,the proposed scheme has advantage over the schemes based on commutative algebraic structures.
Three types of traditional hard problem could be resolved by Shor,Boneh and Lipton's quantum algorithms in po-lynomial time.By the braid group constructed a lot of mathematics difficulties were not an effective solution under the conditions of the quantum computer.It seemed that braid group was a kind of considerable considerable cryptography platform in the future.This paper proposed a new proxy blind signature scheme based on conjugate search problem and the p-th root finding problem,and the exchangeable of the group operation between the elements in the left subgroup and the right subgroup of a braid group.Through program analysis shows that the new scheme is effective and feasible.
Diffie-Hellman key-agreement and RSA cryptosystem are widely used to provide security in internet protocols. But both of the two algorithms are totally breakable using Shor's algorithms. This paper proposes two connected matrix-based key-agreements: (a) Diffie-Hellman Key-Agreement with Errors and (b) RSA-Resemble Key-agreement, which, respectively, bear resemblance to Diffie-Hellman key-agreement and RSA cryptosystem and thereby they gain some of the well-known security characteristics of these two algorithms, but without being subject to Shor's algorithms attacks. That is, the new schemes avoid the direct reliance on the hardness of Discrete Logarithm and Integer Factoring problems which are solvable by Shor's algorithms. The paper introduces a new family of quantum-safe hardness assumptions which consist of taking noisy powers of binary matrices. The new assumptions are derived from Decisional Diffie-Hellman (DDH) assumption in the general linear group GL(n,2) by introducing random noise into a quadruple similar to that which define the DDH assumption in GL(n,2(. Thereby we make certain that the resulting quadruple is secure against Shor's algorithm attack and any other DLP-based attack. Thence, the resulting assumptions, are used as basis for the two key-agreement schemes. We prove that these key-agreements are secure -- in key indistinguishability notion -- under the new assumptions.