Post-Quantum Key Exchange on ARMv8-A: A New Hope for NEON Made Simple

NewHope and NEWHOPE-SIMPLE are two recently proposed post-quantum key exchange protocols based on the hardness of the Ring-LWE problem. Due to their high security margins and performance, there have already been discussions and proposals for integrating them into Internet standards, like TLS, and anonymity network protocols, like Tor. In this work, we present constant-time and vector-optimized implementations of NEWHOPE and NEWHOPE-SIMPLE for ARMv8-A 64-bit processors which target high-speed applications. This architecture is implemented in a growing number of smart phone and tablet processors, and features powerful 128-bit SIMD operations provided by the NEON engine. In particular, we propose the use of three alternative modular reduction methods. They allow to better exploit NEON parallelism by avoiding larger data types during the Number Theoretic Transform (NTT). Furthermore, they remove the need to transform input coefficients into Montgomery domain during pointwise multiplications. The NEON vectorized NTT uses a 16-bit unsigned integer representation and executes in only 18,909 clock cycles on an ARM Cortex-A53 core. Our implementation improves previous assembly-optimized results on ARM NEON platforms and outperforms the c reference implementation on the same platform by a factor of 8.3. The total time spent on the key exchange was reduced by more than a factor of 3.5 for both protocols.