벤트 함수 (Bent Function)

벤트 함수는 입력 변수 개수 n이 짝수일 때 비선형성이 가능한 최댓값에 이르는 부울 함수입니다. 월시 변환의 모든 계수 절댓값이 같아서, 어떤 아핀(선형) 함수와도 상관의 크기가 같고 어느 것으로도 잘 근사되지 않습니다.

자세히 알아보기

부울 함수 f의 비선형성은 f와 가장 가까운 아핀 함수 사이의 해밍 거리(다른 출력 비트 수)입니다. 비선형성이 낮으면 선형 근사로 함수를 흉내 낼 수 있어 선형 암호 분석에 약해집니다.

n변수 부울 함수의 월시 계수 W(a)를 보면, 파시발 등식 때문에 모든 계수의 제곱합은 2²ⁿ으로 고정됩니다. 가장 큰 계수를 가장 작게 만들려면 모든 계수의 절댓값이 2^n/2로 같아야 하고, 이것이 벤트 함수의 조건입니다. 이 값이 정수가 되어야 하므로 벤트 함수는 n이 짝수일 때만 존재합니다. 이때 비선형성은 2^n-1 − 2^{n/2 − 1}이 됩니다. 이 개념은 1976년 O. S. Rothaus의 논문에서 체계적으로 정리되었습니다.

단점도 있습니다. 벤트 함수는 출력의 0과 1 개수가 같지 않아 균형(balanced)이 아닙니다. 그래서 실제 암호 설계에서는 벤트 함수를 그대로 쓰기보다, 약간 비선형성을 양보하고 균형을 맞춘 함수로 변형하거나 S-박스 설계의 재료로 씁니다.

월시 변환으로 보는 벤트 함수

부울 함수 f를 ±1 값으로 바꾼 뒤(0→+1, 1→−1) 월시-하다마드 변환을 하면, 각 계수 W(a)는 f와 선형 함수 a·x의 상관 정도를 나타냅니다. 계수 절댓값이 크면 그 선형 함수와 많이 닮았다는 뜻이고, 이는 선형 암호 분석에서 이용할 수 있는 약점이 됩니다. 비선형성은 다음 식으로 구합니다.

NL(f) = 2ⁿ⁻¹ − max|W(a)| / 2

벤트 함수는 max|W(a)|가 가능한 최솟값 2^n/2이므로 비선형성이 최대가 됩니다. 빠른 월시 변환(FWT)을 쓰면 n·2ⁿ 정도의 연산으로 모든 계수를 계산할 수 있어, 후보 함수가 벤트인지 쉽게 확인할 수 있습니다.

대표적인 구성법

• Maiorana–McFarland 구성: x와 y를 n/2비트씩 나누어 f(x, y) = x·π(y) ⊕ g(y) 형태로 만듭니다. π가 순열이면 f는 벤트 함수입니다.
• 이차 형식: x1x2 ⊕ x3x4 ⊕ … ⊕ x(n−1)xn 같은 함수는 가장 간단한 벤트 함수입니다.

벤트 함수는 대수적 차수가 n/2 이하라는 제약도 있어, 실제 암호 부품으로 쓸 때는 비선형성 외에도 균형성, 대수적 차수, 상관 면역성 같은 여러 기준을 함께 따집니다. S-박스 설계에서는 각 출력 비트의 조합이 높은 비선형성을 갖도록 벤트 함수의 성질을 활용합니다.

쉽게 말하면

어떤 직선 자로 대어 봐도 똑같이 크게 어긋나는, 가장 '구불구불한' 함수입니다.

예시

n = 4이면 출력은 16비트입니다. 무작위 함수라면 아무 아핀 함수와도 평균 8비트 정도 다르지만, 벤트 함수는 모든 아핀 함수와 정확히 6비트 또는 10비트 차이가 납니다. 따라서 비선형성은 2³ − 2¹ = 6이며, 4변수 함수가 가질 수 있는 최댓값입니다. 예: f(x1,x2,x3,x4) = x1·x2 ⊕ x3·x4.