다중순열 (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⁸) 위의 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를 되돌릴 수 있습니다.