**On fractional correlation immunity of majority functions**

*Chuan-Kun Wu*

**Abstract: **The correlation immunity is known as an important cryptographic
measure of a Boolean function with respect to its
resist against the correlation attack. This paper generalizes
the concept of correlation immunity to be of a fractional value, called
fractional correlation immunity, which is a fraction between
0 and 1, and correlation immune function is the extreme case when the
fractional correlation immunity is 1. However when a function is not
correlation immune in the traditional sense, it may also has a nonzero
fractional correlation immunity, which also indicates the resistance
of the function against correlation attack.

This paper first shows how this generalized concept of fractional correlation immunity is a reasonable measure on the resistance against the correlation attack, then studies the fractional correlation immunity of a special class of Boolean functions, i.e. majority functions, of which the subset of symmetric ones have been proved to have highest algebraic immunity. This paper shows that all the majority functions, including the symmetric ones and the non-symmetric ones, are not correlation immune. However their fractional correlation immunity approaches to 1 when the number of variable grows. This means that this class of functions also have good resistance against correlation attack, although they are not correlation immune in the traditional sense.

**Category / Keywords: **foundations / Majority function, correlation immunity

**Publication Info: **Previous version submitted to IEEE-IT in January 2007

**Date: **received 10 Feb 2009

**Contact author: **ckwu at is iscas ac cn

**Available format(s): **PDF | BibTeX Citation

**Note: **The previous version was rejected by IEEE-IT after over 2 years review process. Submission of the paper here is to claim the originality of the relevant concepts and results (if any), mostly available in 2007 instead of 2009.

**Version: **20090210:212835 (All versions of this report)

**Short URL: **ia.cr/2009/067

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]