Cryptology ePrint Archive: Report 2017/1171
Attacks on the AJPS Mersenne-based cryptosystem
Koen de Boer and Léo Ducas and Stacey Jeffery and Ronald de Wolf
Abstract: 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.
Category / Keywords: public-key cryptography / Cryptanalysis, Mersenne, NTRU, Meet-in-the-Middle, Lattice
Original Publication (with minor differences): PQCrypto 2018
Date: received 1 Dec 2017, last revised 25 Jan 2018
Contact author: kboer at cwi nl
Available format(s): PDF | BibTeX Citation
Version: 20180125:131934 (All versions of this report)
Short URL: ia.cr/2017/1171
[ Cryptology ePrint archive ]