Skip to Main content Skip to Navigation
Conference papers

Finding low-weight polynomial multiples using discrete logarithm

Abstract : Finding low-weight multiples of a binary polynomial is a difficult problem arising in the context of stream ciphers cryptanalysis. The classical algorithm to solve this problem is based on a time memory trade-off. We will present an improvement to this approach using discrete logarithm rather than a direct representation of the involved polynomials. This gives an algorithm which improves the theoretical complexity, and is also very flexible in practice.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00123316
Contributor : Yann Laigle-Chapuy <>
Submitted on : Thursday, July 12, 2007 - 9:57:27 AM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on: : Thursday, September 23, 2010 - 4:09:46 PM

Files

DidierLaiglechapuy.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00123316, version 3
  • ARXIV : cs/0701069

Collections

Citation

Frédéric Didier, Yann Laigle-Chapuy. Finding low-weight polynomial multiples using discrete logarithm. IEEE International Symposium on Information Theory - ISIT'07, Jun 2007, Nice, France. ⟨inria-00123316v3⟩

Share

Metrics

Record views

116

Files downloads

245