Cryptology ePrint Archive: Report 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.

Category / Keywords: Stream Cipher, Boolean function, LFSR

Publication Info: A part of the work was presented in INTERNATIONAL CRYPTOLOGY WORKSHOP AND CONFERENCE 2008 (CRYPTOLOGY2008)

Date: received 4 Jul 2009, last revised 7 Jul 2009, withdrawn 5 Oct 2009

Contact author: mehreenafzal00 at hotmail com

Available format(s): (-- withdrawn --)

Version: 20091005:080849 (All versions of this report)

Short URL: ia.cr/2009/329

Discussion forum: Show discussion | Start new discussion