MDS 부호 (MDS Codes)

MDS 부호(MDS code)는 Maximum Distance Separable 코드의 약자로, 같은 길이와 정보량을 가진 코드 가운데 코드워드 사이의 최소 거리가 이론상 최대인 코드입니다. 길이 n, 정보 길이 k, 최소 거리 d인 선형 코드에서는 항상 싱글턴 한계 d ≤ n − k + 1이 성립하며, 이를 등호(d = n − k + 1)로 만족하는 코드를 MDS 코드라고 합니다. MDS 코드는 블록 암호 설계의 와이드 트레일 전략(wide trail strategy)에도 쓰입니다.

오류 정정 능력

MDS 코드는 원래 데이터 k개 기호에 중복 기호 n − k개를 덧붙여 더 긴 표현으로 확장합니다. 최소 거리가 n − k + 1이므로 다음이 가능합니다.

• 위치를 모르는 오류는 최대 ⌊(n − k)/2⌋개까지 정정할 수 있습니다. 그 범위 안에서는 손상된 메시지가 다른 코드워드보다 원래의 올바른 코드워드에 여전히 “더 가깝습니다”.
• 위치를 아는 손실(소실)은 최대 n − k개까지 복구할 수 있습니다. 즉 n개 기호 중 아무 k개만 남아도 원래 데이터를 되살릴 수 있습니다.

같은 중복도에서 이보다 더 많이 복구하는 코드는 없지만, 한도를 넘는 손상은 복구할 수 없습니다. 대표적인 MDS 코드는 리드–솔로몬(Reed–Solomon) 코드입니다. MDS 코드는 충분히 큰 유한체 위에서만 만들 수 있어(대략 길이 n이 체의 크기 q+1을 넘기 어렵습니다) 매개변수 선택에 제약이 있고, 길이가 길수록 인코딩·디코딩 계산량도 커집니다.

저장과 통신에서의 활용

• QR 코드: 리드–솔로몬 코드를 사용하므로 코드의 일부가 가려지거나 손상되어도 정보를 읽을 수 있는 경우가 많습니다.
• RAID와 분산 스토리지: RAID 6이나 이레이저 코딩은 설계된 개수 이내의 드라이브가 고장 나도 남은 드라이브에서 데이터를 복구합니다.
• 통신: 잡음이 많은 채널의 오류 정정과 심우주 통신에 쓰입니다.

암호학에서의 MDS 행렬

블록 암호에서는 MDS 코드의 생성 행렬에서 얻은 MDS 행렬을 확산 계층으로 씁니다. k×k MDS 행렬은 분기 수(branch number)가 최대값 k+1이어서, 입력의 0이 아닌 바이트 수와 출력의 0이 아닌 바이트 수의 합이 항상 k+1 이상입니다. 입력의 작은 변화가 출력의 여러 바이트로 반드시 퍼지므로, 여러 라운드에 걸쳐 활성 S-박스의 수가 커지고 차분·선형 암호 분석이 어려워집니다. 이것이 대먼(Daemen)과 레이먼(Rijmen)의 와이드 트레일 전략이며, AES의 MixColumns는 GF(2⁸) 위의 4×4 MDS 행렬로 분기 수가 5입니다.