Paper 2011/590

An Efficient Broadcast Attack against NTRU

Jianwei Li, Yanbin Pan, Mingjie Liu, and Guizhen Zhu

Abstract

The NTRU cryptosystem is the most practical scheme known to date. In this paper, we first discuss the ergodic-linearization algorithm against GGH, then naturally deduce a new and uniform broadcast attack against several variants of NTRU: for every recipient’s ciphertext, isolate out the blinding value vector, then do derandomization directly and entirety by using inner product, afterwards by using some properties of circular matrix together with linearization we obtain three linear congruence equations of the form aTY = s mod q0 with N + [N2] variables. Hence only if the number of the independent recipients’ ciphertexts/public-keys pairs reaches N + [N2] − 2 can we work out these variables and recover the plaintext in O(N3) arithmetic operations successfully. The experiment evidence indicates that our algorithm can efficiently broadcast attack against NTRU with the highest security parameters. To the best of our knowledge, this is the most efficient broadcast attack against NTRU. This is an algebraic broadcast attack, which is based on the special structure of the blinding value space Lr.