월시 함수 (Walsh Functions)

월시 함수(Walsh Functions)는 본질적으로는 아핀 부울 함수이지만, 종종 값 {+1, -1}로 표현됩니다. 이러한 함수에는 세 가지 다른 정규 순서가 있습니다. 이러한 함수의 가치는 주로 완전한 직교 함수 집합이라는 데 있습니다. 이를 통해 모든 함수를 각 Walsh 함수와의 상관관계로 나타낼 수 있습니다. 이것은 분석 또는 구성을 위해 더 유용할 수 있는 대체 기반으로의 변환입니다.

Walsh 함수란 무엇일까요?

Walsh 함수는 수학적 온/오프 스위치와 같습니다. 0과 1 대신 +1과 -1을 사용합니다. 각 스위치가 켜짐(+1) 또는 꺼짐(-1)인 일련의 라이트 스위치로 생각할 수 있습니다. n개의 입력 비트에 대해 Walsh 함수는 모두 2ⁿ개이며, 각 함수는 입력 비트 일부의 XOR(선형 부울 함수) 값을 +1/-1로 바꾼 것입니다.

변장한 아핀 부울 함수:

+1과 -1로 표현되지만 Walsh 함수는 본질적으로 아핀 부울 함수입니다. 표현 방식만 살짝 바꾼 부울 함수(True 또는 False, 즉 1과 0을 반환)라고 생각해 보세요. 부울 값 0을 +1로, 1을 -1로 대응시키면 XOR 연산이 곱셈으로 바뀌어 계산과 분석이 쉬워집니다.

왜 주목받을까요? 직교성과 완전성

Walsh 함수의 유용성은 다음 두 가지 속성에서 나옵니다:

• 직교성: 서로 다른 두 Walsh 함수를 모든 입력에 대해 곱해 더하면(내적) 0이 됩니다. 즉, 두 함수의 값이 같은 입력과 다른 입력의 수가 정확히 절반씩입니다. 패턴이 “겹치지 않는다”는 뜻이 아니라, 서로 상관관계가 없다는 뜻입니다.
• 완전성: 기본 색상을 결합하여 상상할 수 있는 모든 색상을 만들 수 있는 것처럼, Walsh 함수의 가중 합으로 같은 정의역의 모든 함수를 나타낼 수 있습니다.

Walsh 변환: 분석 도구

직교성과 완전성으로 인해 Walsh 함수는 Walsh 변환(월시-아다마르 변환)의 기초를 형성합니다. 이 변환은 어떤 함수를 Walsh 함수의 조합으로 나타내며, 각 계수는 그 함수가 해당 Walsh 함수와 얼마나 일치하는지(상관관계)를 보여 줍니다. 푸리에 변환이 신호를 사인파로 분해하는 것과 비슷하지만, 기저가 +1과 -1만 갖는 계단형 함수라는 점이 다릅니다. 덧셈과 뺄셈만으로 계산할 수 있는 고속 알고리즘도 있습니다.

암호학에서의 역할

암호학에서 Walsh 변환은 부울 함수와 S-box(치환표)를 평가하는 표준 도구입니다.

• 비선형성 측정: 부울 함수의 Walsh 계수 가운데 절댓값이 가장 큰 값을 보면, 그 함수가 가장 가까운 아핀 함수와 얼마나 다른지(비선형성)를 계산할 수 있습니다. 비선형성이 낮으면 함수를 선형식으로 근사하기 쉬워집니다.
• 선형 암호 분석: 선형 암호 분석은 암호의 입력과 출력 비트 사이의 선형 근사식을 찾는 공격입니다. Walsh 계수는 바로 이런 선형 근사가 성립하는 정도(편향)를 나타내므로, 설계자는 S-box의 Walsh 스펙트럼을 확인해 큰 편향이 없도록 합니다.
• 상관 면역성: 스트림 암호의 결합 함수에서, 출력이 일부 입력 비트와 통계적으로 상관되지 않는지 Walsh 계수로 확인합니다. 상관관계가 있으면 상관 공격에 취약해집니다.

세 가지 정규 순서

Walsh 함수를 배열하는 세 가지 다른 방법이 있습니다. 이를 “정규 순서”라고 합니다.

• 자연 순서(아다마르 순서): 아다마르 행렬의 행 순서를 따릅니다.
• 시퀀시 순서(월시 순서): 함수 값의 부호가 바뀌는 횟수(시퀀시)가 커지는 순서입니다.
• 이진 순서(페일리 순서): 인덱스의 이진 표현에 따라 배열합니다.

각 순서는 해결하려는 문제에 따라 쓰임이 다르지만, 포함된 함수 집합은 같습니다.

장단점

• 계산의 단순성: +1과 -1만 다루므로 덧셈과 뺄셈만으로 변환을 계산할 수 있어 디지털 하드웨어에서 효율적입니다.
• 이산 데이터에 적합: 비트와 부울 함수처럼 본래 이산적인 대상을 분석하는 데 자연스럽게 맞습니다.
• 매끄러움의 제한: 기저 함수가 계단형이므로 매끄럽고 연속적인 신호를 근사하려면 푸리에 변환보다 많은 항이 필요할 수 있습니다.

다른 응용 분야

• 디지털 신호 처리: 필터링, 데이터 압축 및 신호 분석에 사용됩니다.
• 이미지 처리: 이미지 압축, 패턴 인식 및 특징 추출에 적용됩니다.
• 통신 시스템: 이동 통신을 위한 CDMA(code division multiple access) 기술에서 서로 직교하는 확산 부호(월시 부호)로 사용됩니다.

정리하면, Walsh 함수는 형태는 단순하지만 신호 처리, 통신, 암호학 등 여러 분야에서 쓰이는 분석 도구입니다. 특히 암호학에서는 Walsh 변환으로 부울 함수와 S-box의 비선형성과 상관관계를 측정해 선형 공격과 상관 공격에 대한 저항성을 평가합니다.