Paper 2016/1000

Solving Trapdoor Basis of Ideal Lattice from Public Basis

Yupu Hu, 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.

Metadata
Available format(s)
-- withdrawn --
Publication info
Preprint. MINOR revision.
Keywords
Cryptosystems based on ideal latticesTrapdoor basisPublic basis.
Contact author(s)
yphu @ mail xidian edu cn
History
2016-11-18: withdrawn
2016-10-20: received
See all versions
Short URL
https://ia.cr/2016/1000
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.