Hill climbing algorithms and trivium

Julia Borghoff, Lars Ramkilde Knudsen, Krystian Matusiewicz

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    This paper proposes a new method to solve certain classes of systems of multivariate equations over the binary field and its cryptanalytical applications. We show how heuristic optimization methods such as hill climbing algorithms can be relevant to solving systems of multivariate equations. A characteristic of equation systems that may be efficiently solvable by the means of such algorithms is provided. As an example, we investigate equation systems induced by the problem of recovering the internal state of the stream cipher Trivium. We propose an improved variant of the simulated annealing method that seems to be well-suited for this type of system and provide some experimental results.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science
    Number of pages410
    Volume6544
    PublisherSpringer
    Publication date2011
    Pages57-73
    DOIs
    Publication statusPublished - 2011
    Event17th International Workshop on Selected Areas in Cryptography - Waterloo, Canada
    Duration: 12 Aug 201013 Aug 2010
    Conference number: 17

    Workshop

    Workshop17th International Workshop on Selected Areas in Cryptography
    Number17
    CountryCanada
    CityWaterloo
    Period12/08/201013/08/2010
    SeriesLecture Notes in Computer Science

    Keywords

    • Cryptanalysis
    • Trivium
    • Simulated annealing

    Fingerprint Dive into the research topics of 'Hill climbing algorithms and trivium'. Together they form a unique fingerprint.

    Cite this