Construction of correlation immune Boolean functions

It is shown in this paper that every correlation immune Boolean function of \(n\) variables can be written as \(f(x)= g(xG^T)\), where \(g\) is an algebraic non-degenerate Boolean function of \(k\) \((k\leq n)\) variables and \(G\) is an generating matrix of an \([n,k,d]\) linear code. It is known that the correlation immunity of \(f(x)\) is at least \(d-1\). In this paper we further prove when the correlation immunity exceeds this lower bound. A method which can theoretically search exhaustively all possible correlation immune functions is proposed, while constructions of higher order correlation immune functions as well as algebraic nondegenerate correlation immune functions are discussed in particular. It is also shown that many cryptographic properties of \(g\) can be inherited by the correlation immune function \(f(x)= g(xG^T)\) which is an important property for choosing useful correlation immune functions. For the entire collection see [Zbl 0877.00018].

Recommendations

Cited in

(41)

This page was built for publication: Construction of correlation immune Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4373628)