Cryptology ePrint Archive: Report 2020/230

Lattice analysis on MiNTRU problem

Changmin Lee and Alexandre Wallet

Abstract: In ASIACRYPT 2019, Genise et al. describe GGH+19 a new somewhat homomorphic encryption scheme. The security relies on an inhomogeneous and non-structured variant of the NTRU assumption that they call MiNTRU. To allow for meaningful homomorphic computations, they use overstretched parameters, but they do not provide an analysis of their new assumption against the state-of-the-art attack of Kirchner and Fouque KF17 for overstretched modulus. We show that the parameters of GGH+19 do not satisfy the desired security by actually conducting the known analysis. We also report a successful break of the smallest set of parameters in around 15 hours of computations while they are claimed to reach 100 bits of security.

Category / Keywords: MiNTRU, lattice analysis

Date: received 20 Feb 2020, last revised 28 Feb 2020

Contact author: changmin lee at ens-lyon fr,wallet alexandre@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200229:022649 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]