Provable Security Against a Differential Attack

Abstract

The purpose of this paper is to show that there exist DES-like iterated ciphers, which are provably resistant against differential attacks. The main result on the security of a DES-like cipher with independent round keys is Theorem 1, which gives an upper bound to the probability of s-round differentials, as defined in Markov Ciphers and Differential Cryptanalysis by X. Lai et al. and this upper bound depends only on the round function of the iterated cipher. Moreover, it is shown that there exist functions such that the probabilities of differentials are less than or equal to 2^3-n, where n is the length of the plaintext block. We also show a prototype of an iterated block cipher, which is compatible with DES and has proven security against differential attacks.