예상치 못한 거리 (Unexpected Distance)

예상치 못한 거리(unexpected distance)는 암호 연구자 테리 리터(Terry Ritter)가 제안한 용어로, S-box 분석에서 불 함수의 비선형도를 계산할 때 고속 월시 변환(FWT)이 계산해 내는 값들을 가리킵니다. 각 값은 '무작위라면 예상되는 해밍 거리'와 '실제로 측정된 아핀 함수까지의 거리'의 차이입니다. 표준 학술 용어는 아니며, 일반적으로는 월시 계수(Walsh coefficient)라고 부르는 양과 같은 정보입니다.

자세히 알아보기

길이가 같은 두 무작위 비트열을 비교하면 대략 절반의 비트가 같고 절반이 다를 것으로 예상됩니다. 그래서 n변수 불 함수(진리표 길이 2ⁿ)와 임의의 다른 함수 사이의 기대 해밍 거리는 2ⁿ⁻¹입니다.

비선형도 계산에서는 이 기대 거리가 이상적인 기준점이 됩니다. 각 아핀 함수에는 원래 형태와 보수(뒤집은) 형태가 함께 있으므로, 한쪽과의 거리가 절반보다 크면 다른 쪽과의 거리는 절반보다 작아집니다. 따라서 어떤 함수도 모든 아핀 함수로부터 2ⁿ⁻¹보다 멀어질 수는 없습니다.

월시 변환은 각 선형 함수 a·x에 대해 W_f(a) = Σ(−1)^f(x ⊕ a·x)를 계산하는데, 이 값과 거리 사이에는 d(f, a·x) = 2ⁿ⁻¹ − W_f(a)/2라는 관계가 있습니다. 즉 W_f(a)/2가 '기대 거리에서 벗어난 정도', 리터의 말로 예상치 못한 거리입니다. 부호는 원래 형태와 보수 형태 중 어느 쪽에 더 가까운지를 알려 주고, 절댓값은 선형성의 척도입니다. 비선형도는 NL(f) = 2ⁿ⁻¹ − max|W_f(a)|/2로 얻습니다.

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

이 값은 블록 암호와 해시 함수의 비선형 요소를 평가하는 표준 계산의 일부입니다. 지갑 암호화에 쓰이는 AES의 8비트 S-box는 출력 비트의 모든 선형 결합에 대해 최대 |W|가 32여서 비선형도가 2⁷ − 16 = 112입니다. 선형 암호 분석의 성공 확률은 바로 이 최대 월시 계수, 즉 가장 큰 '예상치 못한 거리'에 의해 좌우됩니다.

쉽게 말하면

'무작위라면 절반쯤 달라야 하는데, 실제로는 얼마나 덜 또는 더 다른가'를 잰 값입니다. 그 차이가 작을수록 함수는 선형 함수와 닮지 않아 안전합니다.

예시

3변수 함수 f = x₁x₂(진리표 길이 8)에서 기대 거리는 4입니다. 상수 0 함수와의 거리는 2이므로 W_f(0) = 8 − 2·2 = 4이고, 예상치 못한 거리는 +2입니다.