On computational complexity of impossible differential cryptanalysis

•Introducing a structure for the impossible differential attack on block ciphers.•Introducing the concept of an ideal impossible differential attack.•Proving a tight approximation for the time complexity of an ideal attack.•The proven approximation just depends on the number of involved key bits.

Impossible differential cryptanalysis is one of the conventional methods in the field of cryptanalysis of block ciphers. In this paper, a general model of an impossible differential attack is introduced. Then, according to this model, the concept of an ideal impossible differential attack is defined and it is proven that the time complexity of an ideal attack only depends on the number of involved round key bits in the attack.