The circular pipeline achieving higher throughput in the search for bent functions
Loading...
Authors
Johnson, Christopher D.
Subjects
Advisors
Butler, Jon T.
Stanica, Pantelimon
Date of Issue
2010-09
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
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 encryption systems. A good defense is the use of a primitive based on Boolean functions having the highest nonlinearity possible a bent function. Bent functions are extremely rare and, therefore, difficult to find. The implementation of a sieve on a field programmable gate array (FPGA) provides a high throughput (one function per clock) approach to searching for bent functions. With a clock frequency of 100 MHz, throughput is 100,000,000 functions per second. The circular pipeline as a way to achieve an even higher throughput is examined in this thesis. The theoretical maximum speedup is 2n, where n is the number of variables. The exact achievable speedup has been unknown until now. It is shown that a speedup of 55 is achieved at n = 6 with the design proposed in this thesis, which is 86% of the theoretical maximum.
Type
Thesis
Description
Series/Report No
Department
Electrical Engineering
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
xviii, 96 p. : ill. ;
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.