On the independence of Boolean functions

Abstract

Boolean functions are widely used because they can be used to precisely describe logical circuits. Properties of Boolean functions with respect to their applications to cryptography have been studied, but relationship between Boolean functions are rarely studied. This paper studies the independence of Boolean functions, gives necessary and sufficient conditions for judging whether two given Boolean functions are independent. Some enumeration formulae are given.

Keywords:

• Cryptography
• Boolean function
• Independence

Acknowledgement

This work was supported by the Natural Science Foundation of China No. 90304007 and 973 project 2004CB318004.