Paper 2009/329

Efficient Approximation of Higher Order Boolean function in a Low Order Function

Mehreen Afzal and Ashraf Masood

Abstract

A few of non-linear approximation methods for Boolean functions have been developed but they are not of practical application. However, if a low order Boolean function can be found that can nearly approximate a higher order Boolean function of an encryption technique then the low order Boolean function can be used to exploit the cipher. Such a technique can become a strong cryptanalytic tool and can sneak in a cipher. In this article, an efficient method has been devised to find non-linear low degree approximation of the Boolean function. The algorithm is based on non-linear filter generator followed by solving Galois field 2 equations. To find best approximations execution time of the proposed algorithm is tremendously low as compared the brute force search. Suggested method is very efficient and of practical nature.