Circular Pipeline: Achieving Higher Throughput in the Search for Bent Functions

摘要

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.