Знаходження наближень булевих функцій у певних класах функцій, що мають більш просту будову, є традиційноюзадачею симетричної криптографії. Зокрема, при побудові кореляційних атак на потокові шифри потрібно знаходи-ти наближення булевих функцій від n змінних k -вимірними функціями, тобто такими, що є афінно еквівалент-ними функціям від k ? n змінних. Основним результатом статті є алгоритм побудови списку всіх k -вимірнихфункцій степеня не вище d , які знаходяться на відносній відстані не більше2 (1 ) d ? ? ? від булевої функції n змін-них, що задається вектором її значень, 1? d ? k ? n, ? ?(0,1) . Запропонований алгоритм є більш ефективним упорівнянні з найкращим раніше відомим (у певних випадках – в 1000 та більше разів) і може бути застосований напрактиці при дослідженні кореляційних властивостей функцій ускладнення потокових шифрів.
Нахождение приближений булевых функций в опреде-ленных классах функций, имеющих более простоестроение, является традиционной задачей симметрич-ной криптографии. В частности, при построении кор-реляционных атак на поточные шифры требуется нахо-дить приближения булевых функций от n переменныхk -мерными функциями, то есть такими, которые аф-финно эквивалентны функциям от k ? n переменных.Основным результатом статьи является алгоритм по-строения списка всех k -мерных функций степени невыше d, находящихся на относительном расстоянии неболее 2 (1??) ?d от булевой функции n переменных,заданной вектором ее значений, 1? d ? k ? n , ? ?(0,1).Предложенный алгоритм является более эффективнымпо сравнению с лучшим ранее известным (в некоторыхслучаях – в 1000 и более раз) и может быть использованна практике при исследовании корреляционных свойствфункций усложнения поточных шифров.
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.
