Constructing Correlation Immune Symmetric Boolean Functions

Jie PENG  Haibin KAN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.7   pp.1591-1596
Publication Date: 2011/07/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.1591
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Coding Theory
stream cipher,  correlation attack,  correlation immunity,  symmetric Boolean function,  

Full Text: PDF(100.1KB)>>
Buy this Article

A Boolean function is said to be correlation immune if its output leaks no information about its input values. Such functions have many applications in computer security practices including the construction of key stream generators from a set of shift registers. Finding methods for easy construction of correlation immune Boolean functions has been an active research area since the introduction of the notion by Siegenthaler. In this paper, we present several constructions of nonpalindromic correlation immune symmetric Boolean functions. Our methods involve finding binomial coefficient identities and obtaining new correlation immune functions from known correlation immune functions. We also consider the construction of higher order correlation immunity symmetric functions and propose a class of third order correlation immune symmetric functions on n variables, where n+1(≥ 9) is a perfect square.