IEEE Transactions on Computers

Practical Randomized RLWE-Based Key Exchange Against Signal Leakage Attack

Xinwei Gao, Jíntai Ding, Lin Li, Jiqiang Liu

Published Feb 22, 2018• 32 citations

Abstract

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.

DOI: 10.1109/tc.2018.2808527

Related papers

A Secure and Efficient Randomized RLWE‐based Key Exchange Scheme

Gaurav Mittal, Sandeep Kumar, S. K. Pal

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.

Concurrency and Computation Practice and ExperienceJun 1, 20260 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

Comparison analysis and efficient implementation of reconciliation-based RLWE key exchange protocol

Xinwei Gao, Jíntai Ding, Saraswathy Rv +2 more

Error reconciliation is an important technique for learning with error (LWE) and ring-LWE (RLWE)-based constructions. In this paper, we present a comparison analysis on two error reconciliation-based RLWE key exchange protocols: Ding et al. in 2012 (DING12) and Bos et al. in 2015 (BCNS15). We take them as examples to explain the core idea of error reconciliation, building key exchange over RLWE problem, implementation and real-world performance, and compare them comprehensively. We also analyse a LWE key exchange 'Frodo' that uses an improved error reconciliation mechanism in BCNS15. To the best of our knowledge, our work is the first to present at least 128-bit classic (80-bit quantum) and 256-bit classic (> 200-bit quantum) secure parameter choices for DING12 with efficient portable C/C++ implementations. Benchmark shows that our efficient implementation is 11× faster than BCNS15 and one key exchange execution only costs 0.07 ms on a four-year-old middle range CPU. Error reconciliation is 1.57× faster than BCNS15.

International Journal of High Performance Computing and NetworkingJan 1, 20197 citations

Comparison analysis and efficient implementation of reconciliation-based RLWE key exchange protocol

Jiqiang Liu, Lin Li, Saraswathy Rv +2 more

International Journal of High Performance Computing and NetworkingJan 1, 20190 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

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