# Correlation immunity

﻿
Correlation immunity

In mathematics, the correlation immunity of a Boolean function is a measure of the degree to which its outputs are uncorrelated with some subset of its inputs. Specifically, a Boolean function is said to be correlation-immune of order m if every subset of m or fewer variables in $x_1,x_2,\ldots,x_n$ is statistically independent of the value of $f(x_1,x_2,\ldots,x_n)$.

## Definition

A function $f:\mathbb{F}_2^n\rightarrow\mathbb{F}_2$ is k-th order correlation immune if for any independent n binary random variables $X_0\ldots X_{n-1}$, the random variable $Z=f(X_0,\ldots,X_{n-1})$ is independent from any random vector $(X_{i_1}\ldots X_{i_k})$ with $0\leq i_1<\ldots.

## Results in cryptography

When used in a stream cipher as a combining function for linear feedback shift registers, a Boolean function with low-order correlation-immunity is more susceptible to a correlation attack than a function with correlation immunity of high order.

Siegenthaler showed that the correlation immunity m of a Boolean function of algebraic degree d of n variables satisfies m + d ≤ n; for a given set of input variables, this means that a high algebraic degree will restrict the maximum possible correlation immunity. Furthermore, if the function is balanced then m + d ≤ n − 1.[1]

## References

1. ^ T. Siegenthaler (September 1984). "Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications". IEEE Transactions on Information Theory 30 (5): 776–780. doi:10.1109/TIT.1984.1056949.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Correlation immunity — Die correlation immunity (Korrelationsimmunität) ist ein Maß dafür, ob und wie viel Information man aus dem Funktionswert einer booleschen Funktion über deren Argumente ziehen kann. In der Kryptographie zeigt sie an, wie resistent eine boolesche… …   Deutsch Wikipedia

• Correlation attack — In cryptography, correlation attacks are a class of known plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear feedback shift registers (called LFSRs for the rest of this article)… …   Wikipedia

• Diplomatic immunity — For other uses, see Diplomatic immunity (disambiguation). Diplomatic immunity is a form of legal immunity and a policy held between governments that ensures that diplomats are given safe passage and are considered not susceptible to lawsuit or… …   Wikipedia

• Korrelationsimmunität — Die correlation immunity (Korrelationsimmunität) ist ein Maß dafür, ob und wieviel Information man aus dem Funktionswert einer booleschen Funktion über deren Argumente ziehen kann. In der Kryptographie zeigt sie an, wie resistent eine boolesche… …   Deutsch Wikipedia

• Summation generator — The summation generator, created in 1985, by Rainer Rueppel, was a cryptography and security front runner in the late 1980s. It operates by taking the output of two LFSR s through an adder with carry. The operation s strength is that it is… …   Wikipedia

• List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

• Stream cipher — The operation of the keystream generator in A5/1, a LFSR based stream cipher used to encrypt mobile phone conversations. In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher… …   Wikipedia

• VEST — High Level Structure of VEST General Designers Sean O Neil First published June 13, 2005 Cipher deta …   Wikipedia

• Salsa20 — The Salsa quarter round function. Four parallel copies make a round. General Related to Rumba20, ChaCha Certification eSTREAM portfolio …   Wikipedia

• Panama (cryptography) — Panama General Designers Joan Daemen, Craig Clapp First published February 2002 Derived from StepRightUp Successors MUGI Cipher detail …   Wikipedia