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.
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.
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.
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.
Key Exchange is an essential primitive in cryptography that originated from the breakthrough idea of Diffie Hellman (DH) protocol presented in 1976.Following this work, there are many successful variants of DH using Elliptic curves, Isogeny and RLWE (Ring Learning with Errors).The Ring-Leaning with Errors (RLWE), Search and Decision version are hard problems in mathematics and it has been shown that solving worst case hard problems in ideal lattices can be reduced to solving RLWE in the average case.The reduction forms the basis of provable security for RLWE based key exchange against passive adversaries.The hardness of the decision version of RLWE, which means indistinguishability of RLWE samples from Uniform, makes it challenging to validate a RLWE form public key.This proves to be an advantage for malicious users to create public keys that deviate from a protocol to recover the secret of reused keys in Key Exchange (KE) protocols.In this thesis, we provide a cryptanalysis of RLWE key exchange, presenting two polynomial time strategies to exploit key reuse.Then we propose a defense against such exploits by presenting a Zero Knowledge authentication protocol to verify the prover's knowledge of a secret corresponding to his public key.The protocol is Statistical Zero Knowledge with negligible soundness and completeness errors so that the prover does not reveal any information about the secret in the proof.This is to ensure that a malicious verifier cannot impersonate the prover after the proof.The authentication protocol uses the signal function defined in RLWE key exchange to perform the verification.Firstly, I would like to express my gratitude to my advisor Prof.Ding for his expert advice, strong encouragement and support throughout my PhD study
There are cryptographic systems that are secure against attacks by both classical and quantum computers. One of these systems is the NewHope key encapsulation mechanism (KEM) based on the Ring-learning with error problem (Ring-LWE problem). The Ring-LWE problem is presumed to be hard to solve even on a quantum computer. A KEM scheme allows sharing of a common key between two parts (Alice & Bob). This thesis presents original contributions to the security and analysis of key mismatch and information leakage attacks on NewHope KEM and some vulnerabilities on (small)-Ring-LWE problem (a variant of Ring-LWE problem). The first contribution contains some improvements on key mismatch attacks proposed by Bauer et al. and Qin et al. (Bauer et al., 2019; Qin et al., 2019). These key mismatch attacks retrieve Alices secret key. And, we propose two new methods named Fast Qin and Double Qin. The methods Fast Qin and Double Qin require around 240k and 34k oracle queries, respectively; instead of 840k queries of the Qin et al.s method. Moreover, these two new methods are adapted to retrieve Alices secret key on NewHope-512 (a variant of NewHope). The second contribution analyzes the information leakage of Bobs secret key on NewHope when it is reused. Our result corroborates that Bobs secret key must not be reused since with two communications to Bob, his secret key is leaked. In Ring-LWE problem, a polynomial a is selected randomly and a polynomial b is calculated as b = a.s+e where s is the secret polynomial (selected randomly) and the e is a noise polynomial. Our third contribution shows that in small-Ring-LWE, a variant where polynomials s and e are small, there are values of the public parameter a that leak a large percentage of the coefficients of the secret s. And, the last contribution shows that the secret s can be retrieved successfully if at least 50% of the random known coefficients of s and e are known.
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.
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.