Bent Function Discovery by Reconfigurable Computer

摘要

Bent Boolean functions are important in the encoding/decoding of secure messages. Because they are the most nonlinear of all functions, they are the least susceptible to linear attack. However, bent functions are rare and difficult to discover. The only known way to enumerate all bent functions is by a sieve in which many prospective functions are tested. This is a tutorial description of the process of bent Boolean function discovery by a reconfigurable computer. Specifically, we discuss the use of SRC Computers' SRC-6 reconfigurable computer in sieving through a large number of functions. We show why this process is much faster than on a conventional computer (up to 60,000 times), and we discuss the circular pipeline as a method to improve the throughput even further. The circular pipeline takes advantage of the fact that most functions pass not even one test for bentness. The improvement in throughput due to the circular pipeline depends on the relationship between distances among functions, but it is approximately 500 times better than our present throughput.