Computing algebraic immunity by reconfigurable computer

Abstract

Algebraic immunity (Al) is a property of a Boolean function f that measures its susceptibility to an alebraic attack. If f has a low algebraic immunity and f is used in an encryption protocol, then there are ways to successfully cyrptanalyze the system. As a result, it is important to have an efficient means to compute the alebraic immunity of Boolean functions. Unfortunately, algebraic immunity is one of the most complex cryptographic properties to compute. For example, it is significantly more difficult to compute than nonlinearity. Here, we show the advantage of a reconfigurable computer in computating a function's algebraic immunity. For example, we show that a reconfigurable computer is 4.9 times faster than a conventional computer in this computation for 5-variable computer is 4.9 times fater than a conventional computer in this computation for 5-variable functions. Indeed, we compute the distribution of functions to algebraic immunity for all 5-variable functions, a computation that has not been previously accomplished. Interestingly, the problem we address is to design a logic circuit that computes a characteristic of a logic function.