Cryptology ePrint Archive: Report 2016/1000

Solving Trapdoor Basis of Ideal Lattice from Public Basis

Yupu Hu and Zhizhu Lian and Jiangshan Chen

Abstract: In this paper we present two new attacks on cryptosystems based on principal ideal lattices.

First, we show that, if there is one polynomially large entry in the transformation matrix from trapdoor basis to public basis, we can obtain the trapdoor basis with high probability. Our attack is quite simple, and rarely needs to use any lattice-reduction tools. The key point is that some class of matrices satisfies multiplication commutative law. We use multiplication commutative law to obtain a linear equation of integer variables, and find it not difficult to be solved as long as its rank is larger than half of its number of variables.

Second, we show that, if each entry of the trapdoor basis is polynomially large, we can obtain the trapdoor basis with high probability. This attack is a modified version, and we don't care whether each entry of its transformation matrix is super-polynomially large. The key point is that we can obtain many vectors of the inverse ideal, and we can reduce each of these vectors into polynomially large multiple of its generator.

Category / Keywords: Cryptosystems based on ideal lattices, Trapdoor basis, Public basis.

Date: received 18 Oct 2016, last revised 10 Nov 2016, withdrawn 18 Nov 2016

Contact author: yphu at mail xidian edu cn

Available format(s): (-- withdrawn --)

Version: 20161118:100757 (All versions of this report)

Short URL: ia.cr/2016/1000

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]