상관면역성

수학에서 부울함수의 상관 내성은 부울함수의 출력이 입력의 일부 부분집합과 무관한 정도를 측정하는 척도다. Specifically, a Boolean function is said to be correlation-immune of order m if every subset of m or fewer variables in ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ is statistically independent of the value of ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$.

정의

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

암호화 결과

선형 피드백 이동 레지스터의 결합 함수로 스트림 암호에 사용할 경우, 저차 상관-면역성을 가진 부울 함수는 높은 순서의 상관 관계 내성을 가진 함수보다 상관 공격에 더 취약하다.

지젠탈러는 n 변수의 대수적 정도 d d의 부울함수의 상관관계 내성 m이 m + d n n을 만족한다는 것을 보여주었다. 이는 특정 입력 변수 집합에 대해, 높은 대수적 정도가 가능한 최대 상관관계 내성을 제한한다는 것을 의미한다. 또한, 함수의 균형이 잡히면 m + d - n - 1이다.^[1]

참조

추가 읽기

1. 쿠식, 토마스 W. & 스타니카, 팬틀림론(2009년). "Cryptographic Boolean 함수 및 응용 프로그램". 학술 출판사. ISBN 9780123748904.