Formalization and Systematization of Differential Cryptanalysis Notions

Although differential cryptanalysis is widely employed for iterative block ciphers security analysis, it's basic notions are not properly formalized and relations between them are not systematized (especially related to truncated differentials). We present a formalization of these notions using special binary masks, and use it for their systematization, which allows to show strictly that truncated differential characteristic is the most general notion and non-truncated characteristics, non-truncated differentials and truncated differentials are in fact truncated characteristics under certain conditions. We also formalize the procedure of truncated characteristics concatenation and show that for a Markov cipher the probability of the resultant characteristic is estimated as their product (as it was shown by Lai and Massey for non-truncated characteristics).