Post-Quantum Key Exchange From Learning With Errors Over Rings
draft-khera-lpr-ring-lwe-kex-00

Abstract

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

Authors

Rohit Khera

(Note: The e-mail addresses provided for the authors of this Internet-Draft may no longer be valid.)