Quantum Attacks on Mersenne Number Cryptosystems

Mersenne number based cryptography was introduced by Aggarwal et al. as a potential post-
quantum cryptosystem in 2017. Shortly after the publication Beunardeau et al. propose a lattice based attack significantly reducing the security margins. During the NIST post-quantum project Aggarwal et al. and Szepieniec introduced a new form of Mersenne number based cryptosystems which remain secure in the presence of the lattice reduction attack. The cryptoschemes make use of error correcting codes and have a low but non-zero probability of failure during the decoding phase. In the event of a decoding failure information about the secret key may be leaked and may allow for new attacks.
In the first part of this work, we analyze the Mersenne number cryptosystem and NIST submission Ramstake and identify approaches to exploit the information leaked by decoding failures. We describe different attacks on a weakened variant of Ramstake. Furthermore we pair the decoding failures with a timing attack on the code from the submission package. Both our attacks significantly reduce the security margins compared to the best known generic attack. However, our results on the weakened variant do not seem to carry over to the unweakened cryptosystem. ... mehrIt remains an open question whether the information flow from decoding failures can be exploited to break Ramstake.
In the second part of this work we analyze the Groverization of the lattice reduction attack by Beunardeau et al.. The incorporation of classical search problem into a quantum framework promises a quadratic speedup potentially reducing the security margin by half. We give an explicit description of the quantum circuits resulting from the translation of the classical attack. This description contains, to the best of our knowledge, the first in depth description and analysis of a quantum variant of the LLL algorithm. We show that the Groverized attack requires a large (but polynomial) overhead of quantum memory.