Discovery of bent functions using the Fast Walsh Transform
O'Dowd, Timothy R.
Butler, Jon T.
MetadataShow full item record
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 possible nonlinearity, are uncommon. As the number of variables in a Boolean function increases, bent functions become extremely rare. A method of computing the nonlinearity of Boolean functions using the Fast Walsh Transform (FWT) is presented. The SRC-6 reconfigurable computer allows testing of functions at a much faster rate than a PC. With a clock frequency of 100 MHz, throughput of the SRC-6 is 100,000,000 functions per second. An implementation of the FWT used to compute the nonlinearity of Boolean functions with up to five variables is presented. Since there are 22n Boolean functions of n variables, computation of the nonlinearity of every Boolean function with six or more variables takes thousands of years to complete. This makes discovery of bent functions difficult for large n. An algorithm is presented that uses information in the FWT of a function to produce similar functions with increasingly higher nonlinearity. This algorithm demonstrated the ability to enumerate every bent function for n = 4 without the necessity of exhaustively testing all fourvariable functions.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Gangopadhyay, Sugata; Gangopadhyay, Aditi Kar; Pollatos, Spyridon; Stănică, Pantelimon (2015-07-15);While performing cryptanalysis, it is of interest to approximate a Boolean function in n variables f : Fn → F2 by affine functions. Usually, it is assumed that all the input vectors to a Boolean function are equiprobable ...
An analysis of bent function properties using the transeunt triangle and the SRC-6 reconfigurable computer Shafer, Jennifer L. (Monterey, California: Naval Postgraduate School, 2009-09);Linear attacks against cryptosystems can be defeated when combiner functions are composed of highly nonlinear Boolean functions. The highest nonlinearity Boolean functions, or bent functions, are not common- especially ...
Johnson, Christopher D. (Monterey, California. Naval Postgraduate School, 2010-09);For the first time, the circular pipeline as a means to significantly improve the throughput achieved in the search for bent functions is presented in this thesis. Linear cryptanalysis attack is a threat to modern symmetric ...