Construction of Boolean functions with excellent cryptographic criteria using bivariate polynomial representation

Abstract

A class of $2k$-variable Boolean functions with excellent cryptographic criteria is proposed in this paper, using bivariate polynomial representation (BPR). By comparing known Boolean functions created by the ‘BPR-method’, three conjectures on the relationship between cryptographic criteria and parameter settings are given as guidelines to the research. Then on the basis of certain combinatorial facts and computer experiments, we prove that our functions possess the optimal algebraic immunity k, and validate that, at least for $2k\le 18$, the functions preserve almost perfect immunity against fast algebraic attacks. In addition, we show the functions to be 1-resilient with the maximum algebraic degree of $2k-2$ and give a proof of the lower bound for nonlinearity by means of Gauss sum. Our functions demonstrate great performance in meeting the desired cryptographic criteria for use in the filter model of pseudorandom generators.

Keywords:

• Boolean functions
• algebraic immunity
• fast algebraic attacks
• resiliency
• nonlinearity

2010 AMS Subject Classifications:

• 94A60
• 94A55
• 06E30
• 68P25
• 94C10

Acknowledgments

The authors are grateful to the reviewers and editors for their useful comments and corrections.

Disclosure statement

No potential conflict of interest was reported by the authors.

Funding

This work is supported by the National Science Foundation of China (11290141) and the international cooperation project (2010DFR00700).

ORCID

Zhao Wang http://orcid.org/0000-0002-4405-4938