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.

This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.

Proceedings of the 10th International Workshop on Boolean Problems, Freiberg, Germany, Sept. 19-21, 2012, pp. 225-232, 2011