Computing the Algebraic Immunity of Boolean Functions on the SRC-6 Reconfigurable Computer

Abstract

Boolean functions with high algebraic immunity (AI) are vital in reducing the possibility of utilizing algebraic attacks to break an encryption system. Simple algorithms exist to compute the AI of a given n-variable Boolean function, but the time required to test a large number of functions is much greater on conventional computing systems. AI was computed for all functions through n = 5 using the SRC-6. AI was also computed for n = 5 using a C algorithm. The SRC-6 performed 4.86 times faster than a conventional processor for this computation. It is believed that this is the first enumeration of all 5-variable functions with respect to AI. Monte Carlo trials were performed for n = 6, both on the SRC-6 and utilizing a C algorithm on a conventional processor. These trials provided the first known distribution of AI for 6-variable functions. Some algorithms for computing AI require a conversion between the truth table form of the function and its algebraic normal form. The first known Verilog implementation of a reduced transeunt triangle was developed for this conversion. This reduced form requires many fewer gates and has (n) delay versus (2) n delay for a full transeunt triangle.