Paper 2011/590 Original: eprint.iacr.org/2011/590 ↗
An Efficient Broadcast Attack against NTRU
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
- Preprint.
- History
- 2011-11-24: last updated
- 2011-11-03: published
- Short URL
- https://ia.cr/2011/590
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2011/590}
}