Ph.D. Thesis no. 31
Higher-Order Cryptanalysis of Block Ciphers
April 1999
Abstract
The theme in this thesis is design and analysis of block ciphers. Specifically,
new attacks are described that succesfully break cryptosystems in which the
ciphertext is expressible as evaluations of some low-degree polynomial in the
plaintext with a low but non-neglible probability. The attacks are particularly
efficient against certain ciphers that are provably secure against differential
and linear cryptanalysis.
Several proposed ciphers from the crytographic litterature are either broken
entirely by the new approach or shown to have theoretical weaknesses.
Also multiple links from the theory of error-correcting codes to the design of
block ciphers are demonstrated and results from coding theory are succesfully
applied via this connection to the cryptographical setting.
A new, efficient decoding algorithm for Reed-Muller codes that go beyond half
the minimum distance is described. Aside from its error-correcting applications,
the algorithm is also useful for analysing bit-oriented block ciphers.
Pages: 110
AMS classification: 94
Keywords: Cryptography
