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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Broadcast attackNTRUGGHderandomizationlinerizationcircular matrix
Contact author(s)
lijianwei10 @ mails tsinghua edu cn
History
2011-11-24: revised
2011-11-03: received
See all versions
Short URL
https://ia.cr/2011/590
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/590,
      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{https://eprint.iacr.org/2011/590}},
      url = {https://eprint.iacr.org/2011/590}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.