International Conference on Cloud Computing and Big Data Analytics (ICCCBDA)

A Quantum-Resistant Authenticated Key Exchange Protocol Based on RLWE and Error Reconciliation Mechanism

Wentao Li, Yu Zhou, Jie Chen, Jinhua Wang, Xiangyu Pan, Yu Li

Published Apr 24, 2025• 1 citation

Abstract

The rapid development of quantum computers poses a significant threat to the majority of current authenticated key exchang protocols, designed on the hardness of large integer factorization and discrete logarithm problems. Therefore, it is imperative to develop secure and efficient quantum-resistant authenticated key exchang protocols. This paper designs a new public-key cryptographic scheme for identity authentication based on Ring Learning With Errors (RLWE) problem and error reconciliation mechanism. Based on the scheme, we further design a quantum-resistant authenticated key exchange protocol (AKE). This protocol is provably secure under the standard eCK model and achieves forward secrecy. Compared with other classic key exchange protocols based on the RLWE problem, our protocol shows comprehensive advantages in terms of security, computational complexity, and communication complexity.

DOI: 10.1109/icccbda64898.2025.11030440

Related papers

A Quantum Secure and Efficient RLWE-Based Authenticated Key Exchange Protocol for Mobile Devices

Gaurav Mittal, Saibal Kumar Pal, Dharminder Dharminder

The Ring Learning with Errors (RLWE) problem has emerged as a foundational hardness assumption for post-quantum authenticated key exchange (AKE) protocols. In this paper, we propose a post-quantum and efficient RLWE-Based AKE protocol for mobile devices. We provide formal security reduction in the random oracle model under the decisional RLWE and PRF assumptions. We also show that our scheme is safe against key mismatch attack, signal leakage attack, and provide informal analysis of all standard AKE security properties. Further, we showcase that our scheme also provides perfect forward secrecy and replay attack resistance. Finally, we compare our scheme with several other existing schemes in terms of various security attributes along with computational efficiency to demonstrate its practicality and advantages over the other schemes.

International Journal of Foundations of Computer ScienceOct 17, 20260 citations

A Certificateless Authenticated Key Exchange Protocol Based on Ring Learning with Errors

Luyao Ma, Li Li, Hongfei Yang

Ring learning with errors (RLWE) is used to construct anti-quantum key exchange protocols cryptography algorithms, which is hard to solve for quantum computers. In this work, we provide a certificateless authenticated key exchange protocol based on RLWE problem. This proposed protocol implements user identity authentication by certificateless public key cryptosystem, and uses Ding error reconciled function to eliminate the error caused by the introduction of interference term in RLWE problem. We analyzed the correctness of the protocol in detail, and proved the security of the protocol under the improved extended Canetti-Krawczyk (eCK) security model.

IEEE Joint International Information Technology and Artificial Intelligence Conference (ITAIC)Jun 17, 20222 citations

New Authenticated Key Exchange Scheme Based on Ring Learning with Errors Problem

Xiaopeng Yang, Wenping Ma, Chengli Zhang

Using the hard assumption of Ring-Decision Learning With Errors (Ring-DLWE) in the lattice, a new Authenticated Key Exchange (AKE) scheme is proposed, which is based on the Peikert's reconciliation technique. Under the standard model, the proposed scheme is provably secure in the CK model, which is additionally achieves weak Perfect Forward Secrecy (wPFS). Compared with the current Key Exchange (KE) schemes based on the LWE, the proposed scheme not only protects the shared session key with balanced key derivation function but also resists quantum attacks because of the hard assumption on lattice problem.

Jan 1, 20151 citation

Anonymous Three-Party Quantum-Safe Authenticated Key Agreement with Forward Secrecy: Ring Learning with Errors

Swati Thakur, Hemlal Sahu, Pratik Gupta

Objective: To design a secure and efficient three-party post-quantum authenticated key agreement (AKE) protocol that ensures mutual authentication, user anonymity, and forward secrecy, while resisting both classical and quantum adversaries. Methods: The proposed protocol is constructed using the Ring Learning with Errors (Ring-LWE) assumption, which is widely regarded as quantum-resistant. The scheme enables two users to establish a shared session key through a trusted server over an insecure channel. Cryptographic hash functions, lattice-based operations, and masking techniques are employed to achieve authentication, anonymity, and key confidentiality. Formal correctness proofs, informal security analysis, and comparative performance evaluations are conducted to validate the protocol. Findings: The study describes qualitative benefits like "outperforms current protocols" but lacks specific metrics, such as exact computation costs (e.g., 4913 ns total execution) or communication rounds, and "reduces user-side cost to 2438 ns vs. 5395 ns in Islam et al.". Also, substantially more efficient than pairing- or chaotic-map-based protocols, which incur costs exceeding 12000 ns. Communication overhead is reduced by limiting the exchange to two RLWE-based messages and one server response, avoiding expensive bilinear pairing or biometric hash transmissions. These results demonstrate that the proposed scheme provides stronger security guarantees at a lower computational and communication cost, making it suitable for resource-constrained mobile and IoT environments. Novelty: Unlike existing approaches, the proposed protocol simultaneously guarantees user anonymity, forward secrecy, and quantum resistance in a three-party setting based on Ring-LWE. It overcomes known vulnerabilities in prior schemes and achieves improved efficiency without compromising security, making it a practical and robust solution for post-quantum secure communications. Keywords: Key Establishment, Authentication, Ring Learning with Errors, Anonymous Key Exchange, Post Quantum Forward Secrecy

Indian Journal of Science and TechnologyFeb 26, 20260 citations

Robustly Secure Two-Party Authenticated Key Exchange from Ring-LWE

Xiaopeng Yang, Wenping Ma, Zhang Cheng-li

Using the hard assumption of Ring-Decision Learning With Errors (DLWE) in the lattice, we propose a new authenticated key exchange (AKE) scheme which is based on Peikert’s reconciliation technique. Under the CK+ model, the proposed scheme is provably secure. Compared with the traditional Diffie-Hellman (DH) authenticated key exchange (AKE) schemes, the proposed scheme not only has better efficiency and stronger security but also resists quantum attacks because of the hard assumption on lattice problem. The comparisons between Ring-LWE based ones shows that the proposed scheme protects the shared session key with balanced key derivation function (KDF) compared with those current AKE schemes from LWE.

Jan 1, 20140 citations

Efficient Implementation and Analysis of Ring-LWE Quantum-Secure Key Exchange Protocol

Simran Choudhary, Anil Kumar Gupta

The only known threat to some symmetric cryptographic schemes like DES is Grover’s algorithm that proposes a square root speed-up over classical brute force algorithms. NIST [14] points out that if the key sizes are sufficient, symmetric cryptographic schemes (specifically the Advanced Encryption Standard-AES) are resistant to quantum computers. The development of quantum computer is on full pace, hopefully it might be available in a decade. Thus, it is necessary to develop efficient quantum secure public key cryptosystems to provide safe key exchange in quantum era. In this paper we presented an efficient implementation of a Ring-Learning with errors public key cryptosystem whose security is based on intractability of hard problem on lattices. And comparative analysis of proposed cryptosystem with RSA, ECDH and LWE based key exchange protocols is presented.

Jan 1, 20180 citations