The zeroizing attack is to recover a basis of an ideal generated by a secret element g in Z[X]/(X^n+1) from the zero testing parameter and several encodings in public. It can solve the DLIN and subgroup decision problems, but not the GDDH problem on the GGH scheme for the suggested dimension n due to the hardness of the smallest basis problem and the shortest vector problem on the ideal lattice. In this paper, we propose an algorithm to find a short vector in the ideal lattice (g) by applying a lattice reduction to a sublattice obtained from the Hermit Normal Form of (g). This attack utilizes that the determinant of the lattice (g) is not large. We further show that if (g) has a large residual degree, one can find a short element of (g) in polynomial time of n. In order to resist the proposed attacks, it is required that n= Omega tilde(kappa^2 lambda^3) and the positive generator of (g) intersection with Z is large enough.
Category / Keywords: Multilinear maps, graded encoding schemes, zeroizing attack, Hermite normal form Date: received 13 May 2015 Contact author: jhcheon at snu ac kr, cocomi11@snu ac kr Available format(s): PDF | BibTeX Citation Version: 20150514:140312 (All versions of this report) Short URL: ia.cr/2015/461 Discussion forum: Show discussion | Start new discussion