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

Non-Commutative Key Exchange Protocol

Luis Adrián Lizama-Pérez, José Mauricio López Romero

Published Mar 23, 2022• 2 citations
Publisher

Abstract

We introduce a novel key exchange protocol based on non-commutative matrix multiplication defined in $\mathbb{F}_p^{n \times n}$. The security of our method does not rely on computational problems as integer factorization or discrete logarithm whose difficulty is conjectured. We show that the public, secret and channel keys become indistinguishable to the eavesdropper under matrix multiplication. Remarkably, for achieving a 512-bit security level, the public key is 1024 bits and the private key is 768 bits, making them the smallest keys among post-quantum key exchange algorithms. Also, we discuss how to achieve key authentication, interdomain certification and Perfect Forward Secrecy (PFS). Therefore, Lizama's algorithm becomes a promising candidate to establish shared keys and secret communication between (IoT) devices in the quantum era.

DOI
10.20944/preprints202103.0716.v2

Related papers

Non-Commutative Key Exchange Protocol

Luis Adrián Lizama-Pérez, José Mauricio López Romero

We introduce a novel key exchange protocol based on non-commutative matrix multiplication defined in $\mathbb{Z}_p^{n \times n}$. The security of our method does not rely on computational problems as integer factorization or discrete logarithm whose difficulty is conjectured. We claim that the unique eavesdropper's opportunity to get the secret/private key is by means of an exhaustive search which is equivalent to the unsorted database search problem. Furthermore, we show that the secret/private keys become indistinguishable to the eavesdropper. Remarkably, to achieve a 512-bit security level, the keys (public/private) are of the same size when matrix multiplication is done over a reduced 8-bit size modulo. Also, we discuss how to achieve key certification and Perfect Forward Secrecy (PFS). Therefore, Lizama's algorithm becomes a promising candidate to establish shared keys and secret communication between (IoT) devices in the quantum era.

•May 10, 2021•4 citations

Non-Commutative Key Exchange Protocol

Luis Adrián Lizama-Pérez, José Mauricio López Romero

We introduce a novel key exchange protocol based on non-commutative matrix multiplication. The security of our method does not rely on computational problems as integer factorization or discrete logarithm whose difficulty is conjectured. We claim that the unique opportunity for the eavesdropper to get the private key is by means of an exhaustive search which is equivalent to searching an unsorted database problem. Therefore, the algorithm becomes a promising candidate to be used in the quantum era to establish shared keys and achieve secret communication. Furthermore, to establish a 256-bit secret key the size of the public key only requires 256 bits while the private key occupies just 384 bits. Matrix multiplications can be done over a reduced 4-bit size modulo. Also, we show that in a generalized method, private numbers become indistinguishable and we discuss how to achieve Perfect Forward Secrecy (PFS). As a consequence, Lizama's protocol becomes a promising alternative for Internet-of-Things (IoT) computational devices in the quantum era.

•Mar 30, 2021•1 citation

Non-Invertible Public Key Certificates

Luis Adrián Lizama-Pérez, J. Mauricio López R.

Post-quantum public cryptosystems introduced so far do not define a scalable public key infrastructure for the quantum era. We demonstrate here a public certification system based on Lizama's non-invertible key exchange protocol which can be used to implement a secure, scalable, interoperable and efficient public key infrastructure (PKI). We show functionality of certificates across different certification domains. Finally, we discuss a method that enables non-invertible certificates to exhibit perfect forward secrecy (PFS).

Entropy•Feb 12, 2021•7 citations

Quantum-secure Key Exchange Using Heisenberg Lie Algebras: Design, Analysis and Implementation

Aybeyan Selimi, Muzafer H Saracevic, Suad Bećirović +1 more

Abstract This work introduces a new post-quantum key exchange protocol based on the computational hardness of the Nilpotent Commutator Inversion Problem (NCIP) in Heisenberg Lie algebras over GF(p), where p ≈ 2256. Compared to traditional methods based on integer factorization or discrete logarithms, our scheme relies on the non-linear algebraic properties of nilpotent matrices for quantum security. The protocol performs extremely well in sparse environments with 64-byte public keys requiring 0.024ms for 3 × 3 matrices and 128-bit post-quantum security. Through comprehensive comparison with NIST-standardized schemes (Kyber, SPHINCS+), we show superior performance in memory footprint (0.01KB) and computational overhead, particularly for IoT applications. Experimental evaluation confirms 95.1% success rates for 8 × 8 matrices (256-bit security) with sub-millisecond latency, while security analysis establishes resistance to both classical linear algebra attacks and quantum algorithms (Shor’s, Grover’s) through the NCIP hardness assumption. The work provides concrete parameter recommendations aligned with NIST security levels and demonstrates practical implementation in Python using optimized matrix operations over GF(pn). This Lie algebra-based approach offers a mathematically distinct alternative to existing post-quantum primitives, with particular advantages for scalable, lightweight deployments in edge computing and large-scale networks. Future work directions include hardware acceleration, formal security reductions, and integration with low-power network protocols.

Computer Science•Sep 15, 2025•0 citations

Non-invertible Anonymous Communication for the Quantum Era

Luis Adrián Lizama-Pérez

We introduce a new approach for circuit anonymous communication based on Lizama's non-invertible Key Exchange Protocol (ni-KEP) which has been conceived to work in the quantum era. Lizama's protocol has the smallest key size when compared to main post-quantum schemes thus it becomes a promising alternative for the quantum era. Circuit-based communication can be scaled to support the Hidden Service Protocol (HSP) as well as cross-domain digital certificates that promise greater computing security, speed and efficiency.

arXiv:2103.00598•Feb 28, 2021•0 citations

Key Exchange in the Quantum Era: Evaluating a Hybrid System of Public-Key Cryptography and Physical-Layer Security

Paul Staat, Meik Dörpinghaus, Azadeh Sheikholeslami +3 more

Today's information society relies on cryptography to achieve security goals such as confidentiality, integrity, authentication, and non-repudiation for digital communications. Here, public-key cryptosystems play a pivotal role to share encryption keys and create digital signatures. However, quantum computers threaten the security of traditional public-key cryptosystems as they can tame computational problems underlying the schemes, i.e., discrete logarithm and integer factorization. The prospective arrival of capable-enough quantum computers already threatens today's secret communication in terms of their long-term secrecy when stored to be later decrypted. Therefore, researchers strive to develop and deploy alternative schemes.In this work, we evaluate a key exchange protocol based on combining public-key schemes with physical-layer security, anticipating the prospect of quantum attacks: If a powerful quantum attacker cannot immediately obtain a private key, legitimate parties have a window of short-term secrecy to perform a physical-layer jamming key exchange (JKE) to establish a long-term shared secret. Thereby, the protocol constraints the computation time available to the attacker to break the employed public-key cryptography. In this paper, we outline the protocol, discuss its security, and point out challenges to be resolved.

arXiv:2412.13352•Conference on Information Sciences and Systems•Mar 19, 2025•1 citation
We introduce a novel key exchange protocol based on non-commutative matrix multiplication defined in Fpn×n\mathbb{F}_p^{n \times n}Fpn×n​. The security of our method does not rely on computational problems as integer factorization or discrete logarithm whose difficulty is conjectured. We show that the public, secret and channel keys become indistinguishable to the eavesdropper under matrix multiplication. Remarkably, for achieving a 512-bit security level, the public key is 1024 bits and the private key is 768 bits, making them the smallest keys among post-quantum key exchange algorithms. Also, we discuss how to achieve key authentication, interdomain certification and Perfect Forward Secrecy (PFS). Therefore, Lizama's algorithm becomes a promising candidate to establish shared keys and secret communication between (IoT) devices in the quantum era.
We introduce a novel key exchange protocol based on non-commutative matrix multiplication defined in Zpn×n\mathbb{Z}_p^{n \times n}Zpn×n​. The security of our method does not rely on computational problems as integer factorization or discrete logarithm whose difficulty is conjectured. We claim that the unique eavesdropper's opportunity to get the secret/private key is by means of an exhaustive search which is equivalent to the unsorted database search problem. Furthermore, we show that the secret/private keys become indistinguishable to the eavesdropper. Remarkably, to achieve a 512-bit security level, the keys (public/private) are of the same size when matrix multiplication is done over a reduced 8-bit size modulo. Also, we discuss how to achieve key certification and Perfect Forward Secrecy (PFS). Therefore, Lizama's algorithm becomes a promising candidate to establish shared keys and secret communication between (IoT) devices in the quantum era.
We introduce a novel key exchange protocol based on non-commutative matrix multiplication. The security of our method does not rely on computational problems as integer factorization or discrete logarithm whose difficulty is conjectured. We claim that the unique opportunity for the eavesdropper to get the private key is by means of an exhaustive search which is equivalent to searching an unsorted database problem. Therefore, the algorithm becomes a promising candidate to be used in the quantum era to establish shared keys and achieve secret communication. Furthermore, to establish a 256-bit secret key the size of the public key only requires 256 bits while the private key occupies just 384 bits. Matrix multiplications can be done over a reduced 4-bit size modulo. Also, we show that in a generalized method, private numbers become indistinguishable and we discuss how to achieve Perfect Forward Secrecy (PFS). As a consequence, Lizama's protocol becomes a promising alternative for Internet-of-Things (IoT) computational devices in the quantum era.
Post-quantum public cryptosystems introduced so far do not define a scalable public key infrastructure for the quantum era. We demonstrate here a public certification system based on Lizama's non-invertible key exchange protocol which can be used to implement a secure, scalable, interoperable and efficient public key infrastructure (PKI). We show functionality of certificates across different certification domains. Finally, we discuss a method that enables non-invertible certificates to exhibit perfect forward secrecy (PFS).
Abstract This work introduces a new post-quantum key exchange protocol based on the computational hardness of the Nilpotent Commutator Inversion Problem (NCIP) in Heisenberg Lie algebras over GF(p), where p ≈ 2256. Compared to traditional methods based on integer factorization or discrete logarithms, our scheme relies on the non-linear algebraic properties of nilpotent matrices for quantum security. The protocol performs extremely well in sparse environments with 64-byte public keys requiring 0.024ms for 3 × 3 matrices and 128-bit post-quantum security. Through comprehensive comparison with NIST-standardized schemes (Kyber, SPHINCS+), we show superior performance in memory footprint (0.01KB) and computational overhead, particularly for IoT applications. Experimental evaluation confirms 95.1% success rates for 8 × 8 matrices (256-bit security) with sub-millisecond latency, while security analysis establishes resistance to both classical linear algebra attacks and quantum algorithms (Shor’s, Grover’s) through the NCIP hardness assumption. The work provides concrete parameter recommendations aligned with NIST security levels and demonstrates practical implementation in Python using optimized matrix operations over GF(pn). This Lie algebra-based approach offers a mathematically distinct alternative to existing post-quantum primitives, with particular advantages for scalable, lightweight deployments in edge computing and large-scale networks. Future work directions include hardware acceleration, formal security reductions, and integration with low-power network protocols.
We introduce a new approach for circuit anonymous communication based on Lizama's non-invertible Key Exchange Protocol (ni-KEP) which has been conceived to work in the quantum era. Lizama's protocol has the smallest key size when compared to main post-quantum schemes thus it becomes a promising alternative for the quantum era. Circuit-based communication can be scaled to support the Hidden Service Protocol (HSP) as well as cross-domain digital certificates that promise greater computing security, speed and efficiency.
Today's information society relies on cryptography to achieve security goals such as confidentiality, integrity, authentication, and non-repudiation for digital communications. Here, public-key cryptosystems play a pivotal role to share encryption keys and create digital signatures. However, quantum computers threaten the security of traditional public-key cryptosystems as they can tame computational problems underlying the schemes, i.e., discrete logarithm and integer factorization. The prospective arrival of capable-enough quantum computers already threatens today's secret communication in terms of their long-term secrecy when stored to be later decrypted. Therefore, researchers strive to develop and deploy alternative schemes.In this work, we evaluate a key exchange protocol based on combining public-key schemes with physical-layer security, anticipating the prospect of quantum attacks: If a powerful quantum attacker cannot immediately obtain a private key, legitimate parties have a window of short-term secrecy to perform a physical-layer jamming key exchange (JKE) to establish a long-term shared secret. Thereby, the protocol constraints the computation time available to the attacker to break the employed public-key cryptography. In this paper, we outline the protocol, discuss its security, and point out challenges to be resolved.