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

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.