Cryptology ePrint Archive: Report 2020/1324

Separation Results for Boolean Function Classes

Aniruddha Biswas and Palash Sarkar

Abstract: We show (almost) separation between certain important classes of Boolean functions. The technique that we use is to show that the total influence of functions in one class is less than the total influence of functions in the other class. In particular, we show (almost) separation of several classes of Boolean functions which have been studied in the coding theory and cryptography from classes which have been studied in combinatorics and complexity theory.

Category / Keywords: foundations / Boolean function, Total Influence, Monotone Functions, Bent Functions, Strict Avalanche Criteria, Propagation Characteristic, Plateaued function, Constant Depth Circuits, Linear Threshold Function

Date: received 22 Oct 2020

Contact author: anib_r at isical ac in,aniruddhabiswas535@gmail com,palash@isical ac in

Available format(s): PDF | BibTeX Citation

Version: 20201023:084840 (All versions of this report)

Short URL: ia.cr/2020/1324