Discovery of bent functions using the Fast Walsh Transform
Authors
O'Dowd, Timothy R.
Subjects
Advisors
Butler, Jon T.
Stanica, Pantelimon
Date of Issue
2010-12
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
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.
Type
Thesis
Description
Series/Report No
Department
Electrical Engineering
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
xx, 100 p. ;
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.