Cryptanalysis of Block Ciphers with Probabilistic Non-Linear Relations of Low Degree

Thomas Jakobsen

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


    Using recent results from coding theory, it is shown how to break block ciphers operating on $\GF(q)$ where the ciphertext is expressible as evaluations of an unknown univariate polynomial of low degree $m$ over the plaintext with a typically low but non-negligible probability $\mu$. The method employed is essentially Sudan's algorithm for decoding Reed-Solomon codes beyond the error-correction diameter. The known-plaintext attack needs $n=2m/\mu^2$ plaintext/ciphertext pairs and the running time is polynomial in $n$.Furthermore, it is shown how to discover more general non-linear relations $p(x,y)=0$ between plaintext $x$ and ciphertext $y$ that hold with small probability $\mu$.The second attack needs access to $n=(2m/\mu)^2$ plaintext/ciphertext pairs where $m=\deg p$ and its running time is also polynomial in $n$. As a demonstration, we break up to 10 rounds of a cipher constructed by Nyberg and Knudsen provablysecure against differential and linear cryptanalysis.Key words: Cryptanalysis, block cipher, interpolation attack, non-linear relations, Reed-Solomon codes, Sudan's algorithm.
    Original languageEnglish
    Title of host publicationProceedings of Crypto 98, Lecture Notes in Computer Science 1462
    Publication date1998
    Publication statusPublished - 1998
    EventCrypto 98 - Santa Barbara
    Duration: 1 Jan 1998 → …


    ConferenceCrypto 98
    CitySanta Barbara
    Period01/01/1998 → …

    Cite this