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.
Description
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
Collections
Related items
Showing items related by title, author, creator and subject.
-
A parallel approach in computing correlation immunity up to six variables
Etherington, Carole J.; Anderson, Matthew W.; Bach, Eric; Butler, Jon T.; Stănică, Pantelimon (World Scientific Publishing Company, 2015);We show the use of a reconfigurable computer in computing the correlation immunity of Boolean functions of up to 6 variables. Boolean functions with high correlation immunity are desired in cryptographic systems because ... -
Discovery of bent functions using the Fast Walsh Transform
O'Dowd, Timothy R. (Monterey, California. Naval Postgraduate School, 2010-12);Linear cryptanalysis attacks are a threat against cryptosystems. These attacks can be defended against by using combiner functions composed of highly nonlinear Boolean functions. Bent functions, which have the highest ... -
Computing the Algebraic Immunity of Boolean Functions on the SRC-6 Reconfigurable Computer
McCay, Matthew Eric (Monterey, California. Naval Postgraduate School, 2012-03);Boolean functions with high algebraic immunity (AI) are vital in reducing the possibility of utilizing algebraic attacks to break an encryption system. Simple algorithms exist to compute the AI of a given n-variable Boolean ...