The UMBC Cyber Defense Lab presents
Experimentally Measuring the Circuit Complexity
of One-Way Boolean Functions
Brian Weber, CSEE, UMBC
12:00–1:00pm, Friday, 23 February 2018, ITE 229
I present preliminary results from an exhaustive search for one-way functions in certain classes of small Boolean functions. One-way functions are functions that are easy to compute but hard to invert. They are vital for cryptography, yet no one has proven their existence for arbitrary input sizes. For any bounded circuit model of computation, it is possible to search exhaustively over all possible Boolean functions of restricted size and thereby determine for the searched class the maximum disparity between the complexity of any function and its inverse. Throughout, we assume a circuit model in which each gate has fan-in 2 and fan-out 1.
In his 1985 dissertation at MIT, Steven Boyack carried out the first such search. For any positive integers n and M, let Fn,M denote the set of Boolean functions with n inputs and Moutputs. Using circuit size as the complexity measure, Boyack searched the space of every combinatorial function in F3,3 by searching each of 52 equivalency classes of functions in this space. He found that every function class in this space has an identically sized inverse. He was able to prove that functions do exist with more complex inverses outside the space he searched, but not by more than a constant factor.
In spring 2017, using circuit depth as the complexity measure, I searched all injective functions up to F8,8 whose coordinate functions are in F2,1. A coordinate function in this context refers to the function that computes an individual output bit. In addition, I searched up to F4,4 allowing coordinate functions in F3,1. In the space I searched, the most one-way function has fixed depth of 1, and an inverse depth exactly equal to the input size of the function. That is, for each 2 < n < 9, the hardest inverse in the space I searched has a depth of n, where n is the number of input bits. In addition, a search space allowing a larger fan-in for the coordinate functions did not yield functions less invertible than were found in the original search space.
Brian Weber is a senior BS/MS computer engineering student and SFS scholar at UMBC. He hopes to extend the work presented here into his Master’s thesis next year. Email:
Host: Alan T. Sherman, Support for this research was provided in part by the National Science Foundation under SFS grant 1241576.
The UMBC Cyber Defense Lab meets biweekly Fridays. All meetings are open to the public.