Ding Key Exchange
Kritka Sahni, MS CS
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.
- Key exchange
- The Diffie-Hellman protocol
- RLWE Problem and its computational hardness
- Motivation behind Ding key exchange
- Diffie-Hellman like key exchange
- Basic idea
- Ding Key Exchange Scheme
- Signal Function
- Error Reconciliation Function/Robust Extractor
- Key Exchange using RLWE
- Proof of correctness
- Remarks about security
- 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).
- 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.
- 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.
- RLWE Problem - It is a specialization of the LWE problem and is applicable to polynomial rings over finite fields.
- 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.
- Regev, Oded. "On lattices, learning with errors, random linear codes, and cryptography."
Journal of the ACM (JACM) 56, no. 6 (2009): 34.
- Shor, Peter W. "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer."
SIAM review 41, no. 2 (1999): 303.
Rochester Institute of Technology