Concurrency and Computation Practice and Experience

A Secure and Efficient Randomized RLWE‐based Key Exchange Scheme

Gaurav Mittal, Sandeep Kumar, S. K. Pal

Published Jun 1, 2026• 0 citations

Abstract

ABSTRACT Key exchange protocols allow more than one entity to freshly construct an identical key without knowing it in advance. In recent years, the construction of signal‐based ring learning with error (RLWE) based key exchange protocols (KEPs) has been an important area of post‐quantum research. These protocols derive shared secrets by quantizing noisy ring products in the convolution ring , where and is a prime number. In this paper, we cryptanalyze one of the recently proposed KEP of Pursharthi et al., and show that it is prone to an information‐theoretic signal leakage attack. We then put forward a new protocol, called Masked‐Signal RLWE (MS‐RLWE), and show that it is safe against information‐theoretic signal leakage attack. Additionally, we show that our protocol is semantically secure in the random oracle model and it is also resistant to key mismatch attacks. Finally, we compare our scheme with several other KEPs in terms of computational complexity and resistance with respect to various attacks.

DOI: 10.1002/cpe.70793

Related papers

Practical Randomized RLWE-Based Key Exchange Against Signal Leakage Attack

Xinwei Gao, Jíntai Ding, Lin Li +1 more

Ring Learning With Errors (RLWE)-based key exchange is one of the most efficient and secure primitive for post-quantum cryptography. One common approach to achieve key exchange over RLWE is error reconciliation. Recently, an efficient attack against reconciliation-based RLWE key exchange protocols with reused keys was proposed. This attack can recover a long-term private key if a key pair is reused. We also know that in the real world, key reuse is commonly adopted in applications like the Transport Layer Security (TLS) protocol to improve performance. Directly motivated by this attack, we construct a new randomized RLWE-based key exchange protocol against this attack. Our lightweight approach incorporates an additional ephemeral public error term into key exchange materials, so that this attack no longer works. With the same attack, we practically show that the signal value of our protocol is indistinguishable from uniform random, therefore, this attack no longer works. We explain how the attack fails, present 200-bit classic and 80-bit quantum secure parameter choice, efficient implementations, comparisons and discussion. Benchmark shows our protocol is truly efficient and even faster than related vulnerable protocols.

IEEE Transactions on ComputersFeb 22, 201832 citations

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 Quantum-Resistant Authenticated Key Exchange Protocol Based on RLWE and Error Reconciliation Mechanism

Wentao Li, Yu Zhou, Jie Chen +3 more

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.

International Conference on Cloud Computing and Big Data Analytics (ICCCBDA)Apr 24, 20251 citation

On the security of ring learning with error‐based key exchange protocol against signal leakage attack

Komal Pursharthi, Dheerendra Mishra

Abstract Due to the rapid development of mobile communication and hardware technologies, several mobile‐based web applications have gained popularity among mobile users. Mobile users can utilize these devices to access numerous services over the Internet. To ensure secure communication, different key exchange and authentication (KEA) protocols are proposed and frequently used. However, due to the advent of quantum computers, numerous quantum‐safe KEA protocols are also developed using various complex mathematical problems in ideal lattices. As it is an emerging and developing area, we analyze the security of recently suggested ring learning with error based KEA protocols. The goal of this study is to gain a comprehensive understanding of quantum‐safe KEA mechanisms. For our study, we have considered Dharminder's LWE‐based KEA mechanism and Dharminder and Chandran's LWE‐based KEA mechanism. These protocols enable effective communication and provide a better means for safely transmitting messages between user and server. However, we have discovered that a fundamental security weakness in these methods makes them vulnerable to signal leakage attacks (SLA). Based on our analysis, we demonstrated security weakness against SLA and provide the road‐map for secure construction.

Security and PrivacyMar 14, 20235 citations

Leakage of signal function with reused keys in RLWE key exchange

Jíntai Ding, Saed Alsayigh, Saraswathy Rv +2 more

In this paper, we show that the signal function used in Ring-Learning with Errors (RLWE) key exchange could leak information to find the secret s of a reused public key p = as+2e. This work is motivated by an attack proposed in [1] and gives an insight into how public keys reused for long term in RLWE key exchange protocols can be exploited. This work specifically focuses on the attack on the KE protocol in [2] by initiating multiple sessions with the honest party and analyze the output of the signal function. Experiments have confirmed the success of our attack in recovering the secret.

International Conference on CommunicationsMay 1, 201781 citations

Post-Quantum Key Exchange From Learning With Errors Over Rings

Rohit Khera

This note describes a key exchange method based on the ring-LWE (RLWE) assumption. It builds upon several results, including Regev's landmark quantum reduction from certain worst case lattice problems (approx. GapSVP and SIVP) to random instances of the search variant of a particular learning problem (LWE). It also builds on the follow on work of Lyubashevsky, Peikert and Regev on the average case hardness of the RLWE search variant for polynomially bounded numbers of RLWE samples, along with novel applications of automorphism groups in number fields for a RLWE search to decision reduction (thereby demonstrating pseudorandomness of RLWE in these number fields). Subsequently, these results were adopted for the construction of Diffie-Hellman like key exchange methods by Peikert, and then by Lindner and Peikert followed by Ding and then by Ding, Xie and Lin who proposed efficient variants of such protocols. Subsequent work by Peikert proposed another efficient variant, phrased as a key encapsulation method, incorporating a low bandwidth reconciliation technique allowing two parties to exactly agree on a uniformly distributed secret value from noisy RLWE instances. This was followed by a concrete instantiation with parameter sets by Bos, Costello, Naehrig, Stebila, followed by another instantiation by Alkim, Ducas, Poppelmann and Schwabe with the same ring polynomial but a smaller modulus and a different reconciliation method. Unlike most other public key cryptography based key exchange methods, it is believed that RLWE based key exchange would remain secure in the event that an adversary is able to build a quantum computer. This document is a product of the Crypto Forum Research Group (CFRG).

Oct 24, 20170 citations