Analysis of key reuse attacks on the Post-Quantum-scheme NewHope

Up to now, quantum computers have only been considered a theoreticalthreat to today’s public-key-cryptography. Also, nobody can say exactlyhow long it will take until the first larger quantum computers exist. Butrecently some progress has been made, so this theoretical threat is slowlyturning into a real one. Therefore, the cryptographic research communityhas started to develop new schemes that are also safe against attacks ofquantum computers.One of these new schemes is NewHope from Alkim et al. [2], but aswith all new schemes the best way to build confidence that a scheme isas secure as claimed by the authors is to have it analyzed by the researchcommunity. This work is part of this analysis as we take a look at theso far published attack ideas from Bauer et al. [4] and Qin et al. [36].These are key reuse attacks, which target the passively secure version ofNewHope. We re-implemented the attacks and tested them against theC reference implementation written by the authors of NewHope. Withinthis process it was possible to identify minor and major problems. Whilethe Problem in the approach from Bauer et al. just caused a lower successrate, the improvement from Qin et al. became infeasible. Therefore wedeveloped other improvements, to speed up the attack but also to makeit possible to recover over 99% of the secret keys