Paper 2021/586

A New Approach for finding Low-Weight Polynomial Multiples

Laila El Aimani

Abstract

We consider the problem of finding low-weight multiples of polynomials over binary fields, which arises in stream cipher cryptanalysis or in finite field arithmetic. We first devise memory-efficient algorithms based on the recent advances in techniques for solving the knapsack problem. Then, we tune our algorithms using the celebrated Parallel Collision Search (PCS) method to decrease the time cost at the expense of a slight increase in space. Both our memory-efficient and time-memory trade-off algorithms improve substantially the state-of-the-art. The gain is for instance remarkable for large weights; a situation which occurs when the available keystream is small, e.g. the Bluetooth keystream.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.Inscrypt'21
Contact author(s)
laila elaimani @ gmail com
History
2022-01-16: last of 5 revisions
2021-05-10: received
See all versions
Short URL
https://ia.cr/2021/586
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/586,
      author = {Laila El Aimani},
      title = {A New Approach for finding Low-Weight Polynomial Multiples},
      howpublished = {Cryptology ePrint Archive, Paper 2021/586},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/586}},
      url = {https://eprint.iacr.org/2021/586}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.