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

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

## 자세히 알아보기

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

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

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

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

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

블록체인에서 직접 쓰이는 개념은 아니지만, 블록체인이 의존하는 블록 암호와 해시 함수의 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변수 벤트 함수입니다.

---
출처: https://achivx.kr/glossary/fast-walsh-transform-fwt-%EB%B9%A0%EB%A5%B8-%EC%9B%94%EC%8B%9C-%EB%B3%80%ED%99%98-fwt/ · ACHIVX 용어 사전 · 수정일 2026-10-20