FAST ALGORITHMS FOR CONSTRUCTING k - DIMENSIONAL APPROXIMATIONS OF BOOLEAN FUNCTIONS - Олексійчук, Антон Миколайович; Конюшок, Сергій Миколайович; Сторожук, Артем Юрійович (Ukrainian Information Security Research Journal, 2015)
Finding Boolean functions’ approximations in certainclasses of functions with a simple structure, is a traditionaltask in symmetric cryptography. In particular, correlationattacks on stream ciphers need to find approximations ofn -variable Boolean functions by k -dimensional functions,i.e., the functions, which are affine equivalent tofunctions of k  n variables. Main result of this paper isan algorithm for constructing a list of all k -dimensionalfunctions of degree at most d at relative distance notmore than 2 (1) dfrom a given Boolean function of nvariables, defined by the truth table, 1 d  k  n , (0,1) . The proposed algorithm is more efficient thanthe best previously known (in some cases – to 1000 timesand more) and can be used in practice while studying thecorrelation properties of stream cipher’ complicatingfunctions.