Paper 2011/590

An Efficient Broadcast Attack against NTRU

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


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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Broadcast attackNTRUGGHderandomizationlinerizationcircular matrix
Contact author(s)
lijianwei10 @ mails tsinghua edu cn
2011-11-24: revised
2011-11-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jianwei Li and Yanbin Pan and Mingjie Liu and Guizhen Zhu},
      title = {An Efficient Broadcast Attack against {NTRU}},
      howpublished = {Cryptology ePrint Archive, Paper 2011/590},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.