Narrow-Bicliques: Cryptanalysis of Full IDEA

D. Khovratovich, G. Leurent, C. Rechberger

    Research output: Contribution to journalConference articleResearchpeer-review


    We apply and extend the recently introduced biclique framework to IDEA and for the first time describe an approach to noticeably speed-up key-recovery for the full 8.5 round IDEA.We also show that the biclique approach to block cipher cryptanalysis not only obtains results on more rounds, but also improves time and data complexities over existing attacks. We consider the first 7.5 rounds of IDEA and demonstrate a variant of the approach that works with practical data complexity. The conceptual contribution is the narrow-bicliques technique: the recently introduced independent-biclique approach extended with ways to allow for a significantly reduced data complexity with everything else being equal. For this we use available degrees of freedom as known from hash cryptanalysis to narrow the relevant differential trails. Our cryptanalysis is of high computational complexity, and does not threaten the practical use of IDEA in any way, yet the techniques are practically verified to a large extent.
    Original languageEnglish
    Book seriesLecture Notes in Computer Science
    Pages (from-to)392-410
    Publication statusPublished - 2012
    EventEUROCRYPT 2012 - Cambridge, United Kingdom
    Duration: 15 Apr 201219 Apr 2012


    ConferenceEUROCRYPT 2012
    Country/TerritoryUnited Kingdom
    Internet address


    • Block ciphers
    • Bicliques
    • Meet-in-the-middle
    • IDEA
    • Key recovery.


    Dive into the research topics of 'Narrow-Bicliques: Cryptanalysis of Full IDEA'. Together they form a unique fingerprint.

    Cite this