Paper 2021/146

Boolean Functions from Hyperplane Coverings

Benjamin E. Diamond

Abstract

We give a new mathematical representation of boolean functions over prime fields. We show that any subset of the discrete unit cube can be exactly covered by affine hyperplanes (over a sufficiently large prime field). Any boolean function whose "on-set" has been covered in this way can be evaluated within arithmetic protocols. We study the number of hyperplanes required to cover concrete boolean functions, and provide various interesting and surprising results. Our results yield randomized polynomial encodings in the sense of Ishai and Kushilevitz (FOCS '00) which are smaller than prior known constructions. For example, we obtain depth-three, quasilinearly-sized arithmetic circuits which randomly encode the majority and parity functions. We give practical and implemented applications in secure computation. We finally pose the problem of constructing compact hyperplane coverings of arbitrary prescribed cube subsets. We present a new computational-algebraic algorithm for this problem, applying a new technique for the evaluation of affine spans over prime fields.