Ding Key Exchange

Kritka Sahni, MS CS

Abstract

A key exchange protocol allows two users to exchange keys in an insecure channel without sharing any secret materials in advance. An example is the Diffie-Hellman key exchange protocol. But the hard problems in number theory, like the discrete logarithm problem and the integer factorization problem, are vulnerable to quantum computer attacks. Thus, it is important to find constructions based on problems which are resistant to quantum attacks.

One such class of problems is the RLWE problem, and its hardness is based on the fact that solving the average-case RLWE problem is at least as hard as quantumly solving some worst-case hard lattice problems. This paper will mainly study the Ding Key Exchange scheme which is based on the RLWE problem, and is one of the entries in the round one of the NIST's Post Quantum Cryptography competition. It is based on the LWE variant designed by Jintai Ding, Xiang Xie and Xiaodong Lin in their paper titled, "A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem", and is provably secure against both classical and quantum attacks.

Outline

  1. Key exchange
  2. RLWE Problem and its computational hardness
  3. Motivation behind Ding key exchange
  4. Preliminaries
  5. Ding Key Exchange Scheme
  6. Signal Function
  7. Error Reconciliation Function/Robust Extractor
  8. Key Exchange using RLWE
  9. Performance
  10. Conclusions

Definitions

  1. Provable security - Any level of security that can be proved. Usually its a mathematical proof of security and the aim of the proof is to show that the attacker must solve the underlying hard problem in order to break the security of the modeled system. Such a proof does not consider side-channel attacks or other implementation-specific attacks because they are usually impossible to model without implementing the system (and thus, the proof only applies to this implementation).

  2. Robust Extractor - A deterministic algorithm that enables two parties to extract an identical information from two close elements with the help of an additional hint. In Ding key exchange, a robust extractor helps both the parties to compute the shared key.

  3. LWE Problem - Given q >= 2 and n belonging to the set Z+, the LWE problem can be stated as recovering s, belonging to the set Zn (modulo q), from a sequence of "approximate" linear equations. There is a decision version of the LWE problem, namely DLWE. The goal of the DLWE problem is to distinguish between noisy inner products and uniformly random samples from a distribution of Zn x Z (modulo q). For cryptographic applications, the modulus q is taken to be a polynomial in n.

  4. RLWE Problem - It is a specialization of the LWE problem and is applicable to polynomial rings over finite fields.

Slides

Slides

Term Paper

Term Paper

References

  1. Ding, Jintai, Xiang Xie, and Xiaodong Lin. "A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem." IACR Cryptology EPrint Archive 2012 (2012): 688.
  2. Regev, Oded. "On lattices, learning with errors, random linear codes, and cryptography." Journal of the ACM (JACM) 56, no. 6 (2009): 34.
  3. Shor, Peter W. "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer." SIAM review 41, no. 2 (1999): 303.

Kritka Sahni
Rochester Institute of Technology
kxs4926@cs.rit.edu