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.
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.
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.
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)-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.
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
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.
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).