Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / applications, boolean functions, combinatorial cryptography, number theory

Date: received 10 Feb 2021, last revised 24 Feb 2021

Contact author: benediamond at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210224:200935 (All versions of this report)

Short URL: ia.cr/2021/146


[ Cryptology ePrint archive ]