Post-quantum key exchange - a new hope.

Abstract. Earlier in 2015, Bos, Costello, Naehrig, and Stebila (IEEE Security & Privacy 2015) proposed an instantiation of Peikert's ring-learning-with-errors (Ring-LWE) based key-exchange protocol (PQCrypto 2014), together with an implementation integrated into OpenSSL, with the affirmed goal of providing post-quantum security for TLS. In this work we revisit their instantiation and stand-alone implementation. Specif-ically, we propose new parameters and a better suited error distribu-tion, analyze the scheme's hardness against attacks by quantum com-puters in a conservative way, introduce a new and more efficient error-reconciliation mechanism, and propose a defense against backdoors and all-for-the-price-of-one attacks. By these measures and for the same lat-tice dimension, we more than double the security parameter, halve the communication overhead, and speed up computation by more than a fac-tor of 8 in a portable C implementation and by more than a factor of 20 in an optimized implementation targeting current Intel CPUs. These speedups are achieved with comprehensive protection against timing at-tacks.