Statistical approximation theory for discrete functions with application in cryptanalysis of iterative block ciphers

A statistical approximation of a discrete function is defined as a Boolean equation being satisfied with a probability and accompanied by a Boolean function being statisticaly independent on a subset of variables. Properties of this notion are studied. A constructive test for the statistical independence is formulated. Methods for designing linear ststistical approximations for functions used in iterative block symmetric ciphers are considered. Cryptanalysis algorithms based on solving systems of statistical approximations being linear or nonlinear ones are proposed for symmetric ciphers. The algorithms are based on the maximum likelihood method. Definitions, methods and algorithms are demonstrated by examples taken from DES. Paticularly, it is shown that one of the cryptanalysis algorithms proposed in the paper allows to find 34 key bits for full 16-round DES being based on two known nonlinear approximate equations providing 26 key bits only by Matsui's algorithm.