그룹 메시징 오버헤드 O(N)에서 O(log N)으로 최적화한 MLS 프로토콜 분석

Context

1:1 메시징의 Forward Secrecy와 Post-Compromise Security를 그룹 환경으로 확장 시 발생하는 확장성 문제 분석. 초기 Pairwise Encryption 방식의 선형적 리소스 증가와 Sender Keys 방식의 보안 취약점이라는 기술적 트레이드오프 직면.

Technical Solution

• 개별 채널 구축을 통한 O(N) 메시지 오버헤드를 제거하기 위해 단일 암호화 후 배포하는 Sender Keys 구조 도입
• Sender Keys의 취약한 Post-Compromise Security를 보완하고자 Binary Tree 기반의 Ratchet Tree 구조를 사용하는 MLS(RFC 9420) 설계
• 그룹 멤버를 리프 노드에 배치하고 내부 노드에 중간 키를 저장하여 키 업데이트 전파 경로를 최적화
• 멤버 변경 시 루트 노드까지의 경로만 갱신하는 Commit 메커니즘을 통한 키 교체 비용 절감
• 그룹 상태 버전인 Epoch 개념을 도입하여 메시지 암호화 경계를 명확히 하고 암호학적 감사 추적 가능 구조 구현
• 분산 환경에서 발생하는 Concurrent Commit 문제를 해결하기 위한 상태 충돌 해소 메커니즘 적용