eprint.iacr.org will be offline for approximately an hour
for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between
April 12 and April 14, and some authors have been notified that they need to resubmit their papers.
You are looking at a specific version 20220116:165525 of this paper.
See the latest version.
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
-
CC BY
