기술 요약: NFSA: 2계층 비밀 공유를 통한 단일 서버 기반 비순방향 보안 집계 (Non-Forward Secure Aggregation with One Server via Two Layer Secret Sharing)

1. 문제 정의

연합 학습(Federated Learning, FL)은 데이터를 로컬에 유지하면서 협력적인 모델 학습을 가능하게 하지만, 모델 업데이트(그레디언트)의 전송는 여전히 프라이버시 위험을 초라합니다. 개별 사용자의 입력을 제외하고 오직 집계된 모델만을 서버가 학습할 수 있도록 보장하는 보안 집계 프로토콜이 필요합니다.

기존의 서버 기반 보안 집계 프로토콜은 특히 크로스 디바이스 시나리오에서 두 가지 주요 과제에 직면해 있습니다:

1. 사용자 탈퇴 및 키 전달(Key Forwarding): 사용자 탈퇴를 처리하기 위해, 프로토콜은 종종 샤미르 비밀 공유(Shamir's SS)와 같은 임계치 비밀 공유(Threshold SS)를 사용하여 사용자가 "홀더(holder)"(다른 사용자 또는 위원회)에게 비밀 키를 공유합니다. 단일 서버 설정에서는 사용자들이 직접 통신할 수 없으므로, 서버가 이러한 비밀 공유(secret shares)를 전달해야 합니다. 이러한 전달 방식은 상당한 통신 오버헤드($O(NM)$, 여기서$N$은 사용자 수,$M$은 홀더 수)를 발생시키며, 서버가 전달되는 공유 값을 조작하거나 학습하지 않도록 신뢰해야 하는 보안 위험(종종 인증 암호화가 필요함)을 초래합니다.
2. 통신 효율성: 고차원 모델 파라미터와 대규모 사용자는 대역폭 병목 현상을 일으킵니다. 키-동형 의사 난수 함수(Key-homomorphic Pseudo-Random Function, KhPRF)를 사용하는 최근의 "원샷(one-shot)" 집계 방식은 상호작용 라운드를 줄이지만, "암호문 확장(ciphertext expansion)" 문제를 겪습니다. Almost KhPRF(LWR/LWE 기반)는 사용자 수에 비례하는 노이즈를 도입하여, 간섭을 피하기 위해 모델 업데이트에 추가적인 공간을 필요로 하며, 이는 총 통신량을 증가시킵니다($O(RN \log N)$).

2. 방법론

본 논문은 단일 서버 FL 시나리오를 위해 설계되었으며, 서버가 비밀 데이터를 전달할 필요를 제거하고 새로운 인코딩 방법을 통해 통신 오버헤드를 줄이는 NFSA(Non-Forward Secure Aggregation) 프로토콜을 제안합니다.

2.1 2계층 비밀 공유 (Two-Layer Secret Sharing, TLSS)

전달 문제를 해결하기 위해, 저자들은 서버가 민감한 공유 값을 중계하지 않고도 보안 집계를 가능하게 하는 두 계층의 비밀 공유를 결합한 TLSS를 도입합니다.

• Layer 1 (임계치 SS): 사용자 탈퇴를 처리하기 위해 샤미르 비밀 공유를 사용합니다. 사용자의 비밀(예: KhPRF 키)은 $M$개의 홀더에게 분배되는 공유 값 $s_m$으로 나뉩니다.
• Layer 2 (PRF를 이용한 가법적 SS): 사용자는 $s_m$을 서버로 직접 보내서 전달하게 하는 대신, $s_m$을 두 개의 가법적 공유 값 $s_m = s_{m}^{A1} + s_{m}^{A2} \pmod p$로 나눕니다.
  • $s_{m}^{A1}$은 사용자와 홀더 $P_m$ 사이의 사전 협의된 공유 키 $\kappa_{d,m}$에 의해 생성된 의사 난수 함수(PRF)를 사용하여 생성됩니다.
  • $s_{m}^{A2}$는 $s_m - s_{m}^{A1} \pmod p$로 계산됩니다.
  • 사용자는 $s_{m}^{A2}$만을 서버로 보냅니다.
  • 서버는 태그(tag)를 홀더 $P_m$에게 보내고, 홀더는 자신의 공유 키를 사용하여 $s_{m}^{A1}$을 계산한 뒤 서버로 다시 보냅니다.
  • 서버는 $s_m = s_{m}^{A1} + s_{m}^{A2}$를 재구성하여 샤미르 재구성을 진행합니다.
• 결과: 서버는 사용자 및 홀더 간에 비밀 공유 값을 절대 전달하지 않으므로, $O(NM)$의 전달 오버헤드와 전달 데이터에 대한 인증 암호화 요구 사항을 제거합니다.

2.2 Almost KhPRF를 위한 CRT 인코딩

Almost KhPRF 노이즈로 인한 통신 확장을 해결하기 위해, 저자들은 **중국인의 나머지 정리(Chinese Remainder Theorem, CRT)**에 기반한 새로운 인코딩 방법을 제안합니다.

• 문제점: 기존 방식은 입력 $x_i$를 $y_i = \Delta x_i - F(k_i, \tau)$로 마스킹합니다. 이를 올바르게 디코딩하려면 $\Delta$가 사용자 수 $n$보다 커야 하며, 이는 각 요소의 비트 길이를 $\log_2(n+1)$만큼 증가시킵니다.
• 해결책: 저자들은 CRT를 사용하여 입력 벡터의 $d_c$개 요소를 하나의 정수로 패킹합니다.
  • 입력 요소들을 서로 다른 소수 모듈리 $p_i$로 확장합니다.
  • 이들은 $\mathbb{Z}_{p_c}$ (여기서 $p_c = \prod p_i$) 내의 단일 요소로 결합됩니다.
  • 마스킹된 집계는 이 패킹된 요소들에 대해 수행됩니다.
• 이점: 이는 KhPRF 호출 횟수를 $d_c$ 배만큼 줄여주며, Almost KhPRF 노이즈로 인한 요소별 확장을 방지함으로써 전체 통신량을 크게 감소시킵니다.

2.3 NFSA 프로토콜

프로토콜은 두 단계로 작동합니다:

1. 오프라인 단계 (Offline Phase): 사용자와 디크립터(홀더)는 공유 키를 설정하기 위해 키 합의(Key Agreement, KA)를 수행합니다. 이는 상태가 없는(stateless) 작업이며 한 번만 수행됩니다.
2. 온라인 단계 (Online Phase, One-Shot):
   • 마스킹 (Masking): 각 사용자는 KhPRF 키를 생성하고, TLSS를 통해 이를 공유하며(서버에 가법적 공유 값만 전송), CRT로 패킹된 Almost KhPLF를 사용하여 모델 업데이트를 마스킹합니다.
   • 언마스킹 (Unmasking): 디크립터들은 (TLSS 호모모피즘을 활용하여) 가법적 공유 값의 합을 계산하고 이를 서버에 보냅니다. 서버는 글로벌 KhPRF 키를 재구성하고, 글로벌 마스크를 생성한 후, 집계된 암호문을 언마스킹하여 모델 업데이트를 복구합니다.

3. 주요 기여

1. TLSS 스킴: 단일 서버 FL 환경에서 서버가 비밀 공유를 전달할 필요를 제거하는 새로운 2계층 비밀 공유 스킴입니다. 이는 키 공유를 위한 통신 오버헤드를 줄이고 전달 데이터에 대한 인증 암호화 요구 사항을 제거합니다.
2. Almost KhPRF를 위한 CRT 인코딩: 여러 입력을 배치 처리하기 위해 중국인의 나머지 정리를 활용하는 새로운 입력 인코딩 방법입니다. 이는 KhPRF 호출 횟수를 줄이고, Almost KhPRF 노이즈로 인한 모델 업데이트 확장 문제를 완화하여 계산 및 통신 오버헤드를 모두 낮춥니다.
3. NFSA 프로토콜: TLSS와 CRT 인코딩을 결합한 컴팩트한 원샷 보안 집계 프로토콜입니다. 이는 중간 데이터 전달 없이 단일 서버를 통한 고차원 데이터 집계를 지원합니다.

4. 실험 결과

저자들은 Python으로 프로토콜을 구현하였으며, 이를 (TLSS나 CRT 패킹을 사용하지 않는 Shamir's SS 및 KhPRF 기반의) 최첨단 OPA 스킴과 비교하였습니다.

• TLSS 성능: 전통적인 Shamir's SS 전달 방식과 비교했을 때, TLSS는 50개의 홀더와 비밀을 공유할 때 홀더 통신 오버헤드를 약 57% 줄였고, 계산 시간은 95% (64비트 모듈러스 기준) 단축했습니다. 서버 전달 제거 덕분에 전체 오버헤드는 현저히 낮았습니다.
• CRT 인코딩 성능: CRT 패킹($d_c=4$)을 사용하면 OPA 대비 사용자 마스킹 시간을 3.72배 단축하고 통신 트래픽을 1.40배 줄였습니다.
• 엔드 투 엔드(End-to-End) NFSA 성능:
  • 사용자 오버헤드: 100명의 사용자에 대해, NFSA는 통신 효율성(특히 디크립터 통신)을 거의 100배 개선하였으며, 입력 길이에 따라 사용자 계산 시간을 **51%에서 75%**까지 단축했습니다.
  • 서버 오버헤드: 서버 계산 시간은 약 50% 감소하였고, 서버 통신 트래픽은 OPA 대비 25% 감소하였습니다.
  • 디크립터 오버헤드: 디크립터 통신은 OPA의 ~19MB에서 NFSA의 ~0.19MB로, 거의 100배 가까이 감소하였습니다.

5. 의의 및 주장

본 논문은 NFSA가 단일 서버 보안 집계에서 서버 전달의 핵심 병목 현상을 해결한다고 주장합니다. 비밀 공유 프로세스를 서버의 중계 역할로부터 분리함으로써, 공격 표면(attack surface)을 크게 줄이고 통신 비용을 낮춥니다. CRT 인코딩의 통합은 Almost KhPRF의 효율성을 더욱 최적화하여 고차원 FL 모델에 적용 가능하게 만듭니다.

저자들은 NFSA를 준-정직(semi-honest) 환경을 위한 매우 효율적인 솔루션으로 포지셔닝합니다. NFSA가 SCRAPE나 ZKP와 같은 검증 메커니즘을 갖춘 OPA에 비해 악의적인(malicious) 설정에서의 보안 보장은 약할 수 있지만, 준-정직 모델에서는 훨씬 우수한 효율성을 달성함을 인정합니다. 이 연구는 NFSA가 실제 FL 애플리케이션에 확장 가능하고 실용적임을 시사하지만, 악의적인 설정에 대한 검증 가능성을 확장하고 CRT 패킹된 입력의 검증을 정교화하는 후속 연구가 필요함을 밝히고 있습니다.