고속 월시 변환 (Fast Walsh Transform, FWT)

고속 월시 변환(FWT, Fast Walsh Transform)은 불 함수의 월시 스펙트럼, 즉 그 함수가 각각의 선형(아핀) 불 함수와 얼마나 비슷하거나 다른지를 한꺼번에 계산하는 빠른 알고리즘입니다. 고속 월시-아다마르 변환이라고도 하며, 암호에서는 S-박스와 불 함수의 비선형성을 평가하는 기본 도구입니다.

자세히 알아보기

n개의 입력 비트를 받는 불 함수 f는 길이 N = 2ⁿ의 진리표로 나타낼 수 있습니다. 월시 함수는 입력 비트 일부의 XOR로 정의되는 선형 함수이며, 모두 2ⁿ개가 있습니다. 각 월시 함수와 f의 출력이 일치하는 횟수에서 불일치하는 횟수를 뺀 값이 월시 계수이고, 이 계수들의 모음이 월시 스펙트럼입니다.

모든 계수를 정의대로 하나씩 계산하면 약 N² = 4ⁿ번의 연산이 필요합니다. FWT는 고속 푸리에 변환(FFT)과 같은 '나비(butterfly)' 구조를 이용해 이를 N·log₂N = n·2ⁿ번의 덧셈과 뺄셈으로 줄입니다. 진리표를 ±1 값으로 바꾼 뒤, 간격을 1, 2, 4…로 늘려 가며 짝지은 두 값을 (a+b, a−b)로 바꾸는 단계를 n번 반복하면 됩니다.

월시 계수의 절댓값이 클수록 f가 해당 선형 함수와 상관이 크다는 뜻입니다. 함수의 비선형성은 NL(f) = 2ⁿ⁻¹ − max|W|/2 로 계산되며, 이 값이 작으면 선형 암호 분석에 취약합니다. 모든 계수의 절댓값이 2^n/2로 같아 비선형성이 최대인 함수가 벤트 함수입니다.

FWT는 역변환도 같은 구조로 계산할 수 있습니다. 같은 나비 연산을 한 번 더 적용한 뒤 2ⁿ으로 나누면 원래 진리표가 돌아옵니다. 또 부호 형태의 월시 계수들은 제곱합이 항상 4ⁿ이 된다는 파스발 정리를 만족하므로, 어떤 함수도 모든 선형 함수와 동시에 멀리 떨어질 수는 없습니다. 이 사실이 비선형성에 상한이 존재하는 이유입니다.

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

블록체인에서 직접 쓰이는 개념은 아니지만, 블록체인이 의존하는 블록 암호와 해시 함수의 S-박스를 설계하고 검증할 때 FWT로 비선형성과 상관 면역성을 계산합니다. 영지식 증명과 오류 정정 부호 분야에서도 유사한 아다마르 변환이 쓰입니다.

쉽게 말하면

복잡한 함수가 '단순한 규칙'들 각각과 얼마나 닮았는지를 빠짐없이, 그러면서도 아주 빠르게 재는 자입니다.

예시

n = 2, f(x₁,x₂) = x₁·x₂(AND)의 진리표 [0,0,0,1]을 ±1로 바꾸면 [1,1,1,−1]입니다. 1단계: [2,0,0,2], 2단계: [2,2,2,−2]. 최대 절댓값 2이므로 NL = 2 − 1 = 1이며, 모든 계수 절댓값이 2^2/2=2로 같아 AND는 2변수 벤트 함수입니다.