불 함수 비선형도 (Boolean Function Nonlinearity)

불 함수 비선형도(nonlinearity of a Boolean function) NL(f)는 n변수 불 함수 f의 진리표(길이 2ⁿ)를 가장 가까운 아핀 불 함수의 진리표와 똑같이 만들려면 바꿔야 하는 비트 수, 즉 모든 아핀 함수와의 해밍 거리 중 최솟값입니다. 보통 고속 월시-하다마드 변환(FWT)으로 계산하며, S-box 같은 암호 부품이 선형 근사에 얼마나 강한지를 나타내는 대표 지표입니다.

자세히 알아보기

아핀 불 함수는 a·x ⊕ c(일부 입력의 XOR, 상수 c는 0 또는 1) 꼴이며 n변수에서 2ⁿ⁺¹개입니다. 대수적 정규형(ANF)에서 모든 항이 변수 하나 이하로만 이루어진 함수가 이에 해당합니다.

월시 계수 W_f(a) = Σ_x (−1)^f(x ⊕ a·x)를 쓰면 계산이 간단해집니다. 함수 f와 선형 함수 a·x의 거리는 2ⁿ⁻¹ − W_f(a)/2이고, 보수 함수 a·x ⊕ 1과의 거리는 2ⁿ⁻¹ + W_f(a)/2입니다. 따라서

NL(f) = 2ⁿ⁻¹ − (1/2)·max_a |W_f(a)|

입니다. 2ⁿ개의 월시 계수는 FWT로 O(n·2ⁿ) 연산에 모두 구할 수 있습니다.

파세발 등식 Σ W_f(a)² = 2²ⁿ 때문에 비선형도에는 상한 2ⁿ⁻¹ − 2^n/2−1이 있고, n이 짝수일 때 이 상한을 달성하는 함수를 벤트(bent) 함수라 합니다. 벤트 함수는 균형이 맞지 않아 그대로 쓰기 어렵기 때문에, 실제 설계는 균형성·대수적 차수·상관 면역성과 비선형도 사이의 균형을 찾습니다. S-box의 비선형도는 출력 비트들의 0이 아닌 모든 선형 결합(성분 함수)의 비선형도 중 최솟값으로 정의합니다.

블록체인·암호화폐에서는

• AES S-box: 지갑 백업과 거래소 통신에 쓰이는 AES의 S-box는 모든 성분 함수에서 max|W| = 32여서 비선형도가 128 − 16 = 112입니다. 이는 8비트 순열 S-box에서 알려진 최고값이며, AES가 선형 암호 분석에 강한 근거 중 하나입니다.
• 선형 암호 분석: 공격에 쓰이는 선형 근사의 편향(바이어스)은 |W_f(a)|/2ⁿ⁺¹이므로, 비선형도가 높을수록 공격에 필요한 평문 수가 늘어납니다.
• 해시 함수: 이더리움 Keccak의 χ와 SHA-256의 Ch·Maj도 같은 지표로 평가됩니다. 3변수 Maj의 비선형도는 2입니다.

쉽게 말하면

비선형도는 '이 함수를 직선 같은 단순한 규칙으로 흉내 내려면 최소 몇 군데가 틀리는가'입니다. 많이 틀릴수록 흉내 내기 어려워 안전합니다.

예시

2변수 함수 f = x₁x₂(진리표 0, 0, 0, 1)는 상수 0과 한 비트만 다르므로 NL = 1입니다. 이는 2변수에서 가능한 최댓값 2¹ − 2⁰ = 1과 같아 x₁x₂는 벤트 함수입니다.