연합 학습 (Federated Learning)에서의 정보 이론적 보안 집계 (Secure Aggregation) 용량

보안 집계 (Secure Aggregation)는 업데이트의 프라이버시를 유지하면서 서버가 사용자들의 로컬 업데이트를 집계할 수 있도록 합니다. 기존의 정보 이론적 (Information-theoretic) 문제들은 일반적으로 상관관계가 있는 무작위 키 (Correlated random keys)가 신뢰할 수 있는 제3자 (TTP)에 의해 제공되거나 규정된 그룹 구조를 통해 생성된다고 가정하며, 이러한 상관관계가 있는 키를 설정하기 위한 통신 비용은 종종 무시됩니다. 결과적으로, 일반적인 키 분배 메커니즘 하에서의 근본적인 한계는 알려지지 않은 상태로 남아 있습니다. 본 논문에서는 키 분배 단계 (Key distribution phase)와 업데이트 집계 단계 (Update aggregation phase)로 구성된 일반적인 2단계 프레임워크 하에서 $N$ 명의 사용자를 대상으로 하는 $T$-공모 (T-colluding) 정보 이론적 보안 집계 문제를 연구합니다. 이전 연구와 달리, 우리는 사용자 간 통신을 통해 키 분배를 모델링하고 임의의 사용자 생성 키 분배 메커니즘을 허용함으로써 TTP나 규정된 구조를 배제합니다. 이를 통해 보안을 위한 무작위성 (Randomness), 키 분배 통신 (Key-distribution communication), 그리고 집계 통신 (Aggregation communication)이라는 세 가지 자원의 공동 특성화를 가능하게 합니다. 우리는 새로운 보안 집계 스킴 (Secure aggregation scheme)과 그에 부합하는 정보 이론적 역증명 (Information-theoretic converse)을 구축함으로써 이 세 가지 자원 사이의 용량 영역 (Capacity region)을 완전히 규명합니다. 특히, 우리는 크기가 최소 $N$ 이상인 임의의 유한체 (Finite field) 상에서 명시적인 결정론적 용량 달성 구조 (Deterministic capacity-achieving construction)를 개발하였으며, 이는 대부분의 기존 스킴들이 TTP에 의존하거나 충분히 큰 유한체 상에서 무작위적 또는 존재론적 구조를 사용하는 것과 대조적입니다. 나아가 우리는 쌍별 공유 키 (Pairwise shared keys)만을 사용하여 최적의 성능을 달성할 수 있음을 보여주며, 이를 통해 Diffie--Hellman 키 교환을 통한 구현을 가능하게 합니다. Google의 중대한 보안 집계 스킴과 비교했을 때, 제안된 스킴은 동일한 집계 통신 오버헤드를 유지하면서도 더 적은 수의 무작위 마스킹 키 (Random masking keys)를 요구합니다.