Aggarwal, Joux, Prakash and Santha recently introduced a new potentially quantum-safe public-key cryptosystem, and suggested that a brute-force attack is essentially optimal against it. They consider but then dismiss both Meet-in-the-Middle attacks and LLL-based attacks. Very soon after their paper appeared, Beunardeau et al. proposed a practical LLL-based technique that seemed to significantly reduce the security of the AJPS system. In this paper we do two things. First, we show that a Meet-in-the-Middle attack can also be made to work against the AJPS system, using locality-sensitive hashing to overcome the difficulty that Aggarwal et al. saw for such attacks. We also present a quantum version of this attack. Second, we give a more precise analysis of the attack of Beunardeau et al., confirming and refining their results.

doi.org/10.1007/978-3-319-79063-3_5
Lecture Notes in Computer Science
WISE Women In Science Excel , Quantum Computation with Bounded Space
International Conference on Post-Quantum Cryptography
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

de Boer, K., Ducas, L., Jeffery, S., & de Wolf, R. (2018). Attacks on the AJPS Mersenne-based cryptosystem. In PQCrypto 2018: Post-Quantum Cryptography (pp. 101–120). doi:10.1007/978-3-319-79063-3_5