Correlation immunity

The correlation immunity is a measure of whether and how much information can be drawn from the function value of a Boolean function about its arguments.

In cryptography , it shows how resistant a Boolean function is to correlation attacks. The concept of correlation immunity for Boolean functions was first defined by Siegenthaler.

definition

Let be a Boolean function and be binary independent and identically distributed random variables that represent the arguments for . A function is correlation-immune of order if and only if the function value is statistically independent of the input values , specifically for each selection from indices (or less) with . The statement that the mutual information of the or fewer input values and the function value is equal to 0 is directly equivalent to this ${\displaystyle f\colon \mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}}$ ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle m}$ ${\displaystyle f(X_{1},X_{2},\dots ,X_{n})}$ ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$ ${\displaystyle m}$ ${\displaystyle i_{1},i_{2},\ldots ,i_{m}}$ ${\displaystyle 1\leq i_{1}<i_{2}<\ldots i_{m}\leq n}$ ${\displaystyle m}$ ${\displaystyle X_{i_{1}},X_{i_{2}},\ldots ,X_{i_{m}}}$ ${\displaystyle f(X_{1},X_{2},\dots ,X_{n})}$

${\displaystyle I(X_{i_{1}},X_{i_{2}},\ldots ,X_{i_{m}};f(X_{1},X_{2},\dots ,X_{n}))=0.}$

If the function is also evenly distributed, that is , then it is called -resilient. ${\displaystyle f}$ ${\displaystyle \Pr(f(X_{1},\ldots X_{n})=0)=\Pr(f(X_{1},\ldots X_{n})=1)={\frac {1}{2}}}$ ${\displaystyle f}$ ${\displaystyle m}$

But this necessary condition only says whether a function is correlation immune or not. It would be better to find a value for a function that indicates the level of immunity. This is exactly what is required for the definition of the Siegenthaler bound .

Trade-off between correlation immunity and degree of ${\displaystyle f}$

In addition to defining correlation immunity, Siegenthaler also gives an important trade-off between correlation immunity and the degree of a function . If correlation-immune of order is , the degree of . If it is also evenly distributed, i.e. -resilient, then the degree of is even . ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle m}$ ${\displaystyle 1\leq m\leq n-1}$ ${\displaystyle f}$ ${\displaystyle \deg(f)\leq n-m+1}$ ${\displaystyle f}$ ${\displaystyle m}$ ${\displaystyle f}$ ${\displaystyle \deg(f)\leq n-m}$

This means that the correlation immune functions of the highest order always have a small degree. For example, -resilient functions are always of degree 1 or less, i.e. linear or affine . ${\displaystyle (n-1)}$

swell

1. ^ T. Siegenthaler: Correlation immunity of nonlinear combining functions for cryptographic applications (Corresp.) . In: IEEE Transactions on Information Theory . tape 30 , no. 5 , September 1984, ISSN  0018-9448 , pp. 776-780 , doi : 10.1109 / tit.1984.1056949 ( ieee.org [accessed February 14, 2018]).
2. ^ B. Chor, O. Goldreich, J. Hasted, J. Freidmann, S. Rudich: The bit extraction problem or t-resilient functions . In: 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) . October 1985, p. 396-407 , doi : 10.1109 / SFCS.1985.55 ( ieee.org [accessed February 14, 2018]).

Web links

• T. Siegenthaler: Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications . In: IEEE Transactions on Information Theory . 30, No. 5, September 1984, pp. 776-780. doi : 10.1109 / TIT.1984.1056949 .
• http://www.iaik.tugraz.at/teaching/00_angewandte%20kryptografie/slides2008/streamciphers.pdf (PDF file; 15 kB)