# 다중순열 (Multipermutation)

다중순열(multipermutation)은 클라우스 슈노어(C. P. Schnorr)와 세르주 보드네(S. Vaudenay)가 1993년 FSE(고속 소프트웨어 암호화) 워크숍에서 발표한 「병렬 FFT 해싱(Parallel FFT-Hashing)」 논문에서 '확산과 혼돈을 완벽하게 만들어 내는 암호 원시 연산'으로 정의한 개념입니다. 집합 E에 대해 순열 B: E² → E², B(a,b) = (B₁(a,b), B₂(a,b))가 있을 때, 모든 a, b에 대해 B_i(a,·)와 B_i(·,b)(i = 1, 2)가 E 위의 순열이면 B를 다중순열이라고 합니다.

## 자세히 알아보기

이 조건을 풀어 쓰면, 두 입력 중 하나만 바뀌어도 두 출력이 모두 반드시 바뀐다는 뜻입니다. 네 값(입력 2개, 출력 2개) 중 아무 두 개만 알면 나머지 두 개가 정해지는 구조이기도 합니다. 이는 블록 암호 설계에서 말하는 '완전 확산(perfect diffusion)'의 가장 작은 단위입니다.

조합론적으로 보면 B₁과 B₂는 각각 라틴 방진이고, 두 방진을 겹쳤을 때 모든 순서쌍이 정확히 한 번씩 나타나므로 서로 직교하는 라틴 방진 쌍과 같습니다. 테리 리터(Terry Ritter)가 제안한 '균형 블록 혼합(Balanced Block Mixing)'도 같은 구조(직교 라틴 방진)에 기반합니다. 이후 보드네는 r개 입력·n개 출력으로 일반화한 (r,n)-다중순열을 연구했는데, 이는 오늘날 MDS(최대 거리 분리) 부호로 만든 선형 확산 층과 같은 성질을 표현합니다.

주의할 점은 조합론에서 '중복을 허용한 순열'을 가리키는 '다중집합의 순열(permutation of a multiset)'과는 전혀 다른 개념이라는 것입니다. '원소가 여러 번 나올 수 있는 순열'은 암호학의 다중순열이 아닙니다.

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

다중순열이라는 이름이 직접 쓰이지는 않지만, 그 성질은 현대 암호의 확산 층에 그대로 살아 있습니다. AES의 MixColumns는 GF(2^8) 위의 MDS 행렬로, 입력 4바이트 중 1바이트만 바뀌어도 출력 4바이트가 모두 바뀌며(분기 수 5), 이는 다중순열 개념의 일반화입니다. 지갑 파일 암호화와 TLS에 쓰이는 AES가 차분·선형 공격에 강하다는 설계 논증(넓은 경로 전략)은 이런 확산 성질에 기반합니다. 영지식 증명용 해시 함수인 Poseidon도 MDS 행렬을 선형 층으로 사용합니다.

## 쉽게 말하면

두 칸짜리 섞개인데, 어느 입력 하나만 살짝 바꿔도 출력 두 칸이 모두 달라지도록 만든 장치입니다.

## 예시

E = GF(p)에서 B(a,b) = (a + b, a + 2b)는 다중순열입니다. 한 입력을 고정하면 각 출력은 다른 입력에 대한 일대일 함수이고(b ↦ a + 2b가 순열이려면 2의 역원이 있어야 하므로 p ≠ 2), u = a + b, v = a + 2b에서 b = v − u, a = 2u − v로 a, b를 되돌릴 수 있습니다.

---
출처: https://achivx.kr/glossary/multipermutation-%EB%8B%A4%EC%A4%91%EC%88%9C%EC%97%B4/ · ACHIVX 용어 사전 · 수정일 2026-10-20