2025-11-23T13:58:16.869352

Multi-Message Secure Aggregation with Demand Privacy

Sun, Zhang, Wan et al.
This paper considers a multi-message secure aggregation with privacy problem, in which a server aims to compute $\sf K_c\geq 1$ linear combinations of local inputs from $\sf K$ distributed users. The problem addresses two tasks: (1) security, ensuring that the server can only obtain the desired linear combinations without any else information about the users' inputs, and (2) privacy, preventing users from learning about the server's computation task. In addition, the effect of user dropouts is considered, where at most $\sf{K-U}$ users can drop out and the identity of these users cannot be predicted in advance. We propose two schemes for $\sf K_c$ is equal to (1) and $\sf 2\leq K_c\leq U-1$, respectively. For $\sf K_c$ is equal to (1), we introduce multiplicative encryption of the server's demand using a random variable, where users share coded keys offline and transmit masked models in the first round, followed by aggregated coded keys in the second round for task recovery. For $\sf{2\leq K_c \leq U-1}$, we use robust symmetric private computation to recover linear combinations of keys in the second round. The objective is to minimize the number of symbols sent by each user during the two rounds. Our proposed schemes have achieved the optimal rate region when $ \sf K_c $ is equal to (1) and the order optimal rate (within 2) when $\sf{2\leq K_c \leq U-1}$.
academic

수요 프라이버시를 갖춘 다중 메시지 안전 집계

기본 정보

  • 논문 ID: 2504.20639
  • 제목: Multi-Message Secure Aggregation with Demand Privacy
  • 저자: Chenyi Sun, Ziting Zhang, Kai Wan (화중과기대학교), Giuseppe Caire (베를린공과대학교)
  • 분류: cs.IT math.IT
  • 발표 시간: 2025년 10월 13일 (arXiv v2)
  • 논문 링크: https://arxiv.org/abs/2504.20639

초록

본 논문은 K명의 분산 사용자로부터의 로컬 입력에 대해 Kc≥1개의 선형 결합을 계산하려는 서버를 목표로 하는 수요 프라이버시를 갖춘 다중 메시지 안전 집계 문제를 연구한다. 본 문제는 두 가지 작업을 해결한다: (1) 보안성 - 서버가 요청된 선형 결합만 획득하고 사용자 입력의 다른 정보는 유출되지 않도록 보장; (2) 프라이버시성 - 사용자가 서버의 계산 작업을 알지 못하도록 방지. 또한 최대 K-U명의 사용자가 오프라인 상태가 될 수 있고 그 신원을 미리 예측할 수 없는 사용자 이탈의 영향을 고려한다. 저자들은 Kc=1과 2≤Kc<U의 두 가지 경우에 대해 각각 두 가지 방안을 제시한다. Kc=1의 경우, 난수 변수를 사용하여 서버 수요를 곱셈 암호화하는 방법을 도입하고, 2≤Kc<U의 경우 강건한 대칭 프라이빗 계산을 사용하여 두 번째 라운드에서 키의 선형 결합을 복구한다.

연구 배경 및 동기

문제 정의

연합 학습은 분산 사용자가 중앙 서버의 조율 하에 협력하여 전역 모델을 훈련할 수 있게 하지만, 모델 업데이트는 여전히 사용자 로컬 데이터의 정보를 유출할 수 있다. 보안을 더욱 강화하기 위해 안전 집계가 도입되어 서버가 집계된 업데이트만 획득하고 사용자 데이터의 추가 정보는 획득하지 않도록 보장한다.

연구 동기

  1. 다중 작업 학습 수요: 단일 작업 대비 다중 작업 학습은 여러 결과를 활용하여 모델 훈련의 전체 성능을 향상시킬 수 있으며, 정보 및 자원 공유를 통해 학습 효율을 높인다.
  2. 기존 방법의 한계:
    • 기존 정보 이론적 안전 집계 문제는 주로 Kc=1 경우에 초점
    • 서버 계산 작업의 프라이버시 보호 부재
    • 사용자 이탈 상황에서 보안성과 프라이버시성 보장 필요
  3. 실제 응용 수요: 실제 연합 학습 시나리오에서 서버는 여러 개의 서로 다른 선형 결합을 계산해야 할 수 있으며, 사용자는 서버의 구체적인 계산 수요를 알아서는 안 된다.

핵심 기여

  1. 새로운 문제 형식화: 수요 프라이버시를 갖춘 다중 메시지 안전 집계 문제를 처음으로 제시하여 기존 안전 집계 연구 범위를 확장했다.
  2. 최적 방안(Kc=1): 곱셈 암호화 수요와 가법 암호화 모델을 결합한 안전 집계 방안을 제시하여 최적 통신 속도 영역을 달성했으며, 이는 프라이버시 제약이 없는 안전 집계 문제의 용량과 같다.
  3. 근사 최적 방안(2≤Kc<U): 대칭 프라이빗 계산 방안을 활용하여 첫 번째 방안을 Kc번 반복하는 기본 방법을 크게 개선했으며, 첫 번째 라운드 속도는 최적이고 두 번째 라운드 속도는 계수 2 내에서 최적이다.
  4. 이론적 분석: 완전한 도달 가능성 증명과 역방향 경계 분석을 제공하여 문제의 이론적 기초를 확립했다.

방법 상세 설명

시스템 모델

참여자:

  • 1개의 서버와 K명의 비공모 사용자(K≥2)
  • 사용자 i는 입력 벡터 Wi와 키 Pi를 보유
  • Wi는 유한체 Fq 위에 정의된 L개의 독립 동일 분포 균등 기호 포함

목표 함수: 서버는 선형 매핑을 계산: g(W1,⋯ ,WK)=F[W1,⋯ ,WK]Tg(W_1, \cdots, W_K) = F[W_1, \cdots, W_K]^T

여기서 F는 Kc×K 차원 계수 행렬: F=(a1,1⋯a1,K⋮⋱⋮aKc,1⋯aKc,K)F = \begin{pmatrix} a_{1,1} & \cdots & a_{1,K} \\ \vdots & \ddots & \vdots \\ a_{K_c,1} & \cdots & a_{K_c,K} \end{pmatrix}

통신 모델:

  • 첫 번째 라운드: 서버가 사용자 i에게 쿼리 Q1,i를 전송하고, 사용자 i는 메시지 Xi를 반환
  • 두 번째 라운드: 서버가 생존 사용자 집합 U1을 알리고, 쿼리 Q^{U1}_{2,i}를 전송하며, 사용자 i는 Y^{U1}_i를 전송

제약 조건

  1. 복호화 가능성: 서버가 요청된 선형 결합을 오류 없이 계산 가능
  2. 보안성: 서버가 목표 계산 결과를 초과하는 사용자 입력 정보 획득 불가
  3. 프라이버시성: 사용자가 서버의 수요 행렬 F를 추론 불가

Kc=1 경우의 방안

핵심 아이디어

곱셈 암호화 수요와 가법 암호화 모델을 결합하여 난수 변수 t를 통해 서버 수요를 암호화한다.

상세 단계

단계 1 (쿼리 생성):

  • 서버가 t ∈ Fq{0}을 무작위로 선택
  • 쿼리 정의: Q1,i=1ta1,iQ_{1,i} = \frac{1}{ta_{1,i}}, i ∈ K

단계 2 (키 생성):

  • 각 사용자 i에 대해 Zi를 생성하며, F^L_q 위에 균등 분포
  • Zi를 U개의 부분 키로 분할: Zim ∈ F^{L/U}_q
  • MDS 행렬 M을 사용하여 인코딩: [Z~i]j=([Zi]1,…,[Zi]U)⋅M:,j[\tilde{Z}_i]_j = ([Z_i]_1, \ldots, [Z_i]_U) \cdot M_{:,j}

단계 3 (첫 번째 라운드 전송):

  • 사용자 i가 전송: Xi=Wi+Q1,iZiX_i = W_i + Q_{1,i}Z_i

단계 4 (두 번째 라운드 전송):

  • 사용자 j ∈ U1이 집계 인코딩 부분 키 전송: ∑i∈U1[Z~i]j\sum_{i \in U_1}[\tilde{Z}_i]_j
  • 서버가 MDS 복호화를 통해 ∑i∈U1Zi\sum_{i \in U_1} Z_i 복구

복호화 과정

서버가 계산: ∑i∈U11Q1,iXi=∑i∈U11Q1,iWi+∑i∈U1Zi\sum_{i \in U_1} \frac{1}{Q_{1,i}}X_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i + \sum_{i \in U_1} Z_i

t∑i∈U1a1,iWi=∑i∈U11Q1,iWit \sum_{i \in U_1} a_{1,i}W_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i이므로, 서버는 목표 선형 결합을 복호화할 수 있다.

2≤Kc<U 경우의 방안

핵심 아이디어

두 번째 라운드 전송에서 강건한 대칭 프라이빗 계산을 활용하여 보안성과 프라이버시성을 보장한다.

상세 단계

단계 1 (키 생성):

  • 각 i ∈ K에 대해 F^L_q에서 무작위로 Zi 선택
  • 모든 사용자가 공유하는 키: Pi = (Zi)i∈K
  • L/(U-1)개의 공용 난수 변수를 키 마스크로 공유

단계 2 (첫 번째 라운드 전송):

  • 사용자 i가 전송: Xi=Wi+ZiX_i = W_i + Z_i

단계 3 (두 번째 라운드 전송):

  • 서버가 Kc개의 키 결합 복구 필요: ∑i∈U1an,iZi\sum_{i \in U_1} a_{n,i}Z_i, n ∈ Kc
  • 각 키 Zi를 길이 L' = U-1의 부분 키로 분할
  • 각 선형 결합을 획득하기 위해 대칭 프라이빗 계산 방안을 Kc번 사용
  • 라그랑주 인코딩을 통해 쿼리 다항식을 구성하여 계산 작업 프라이버시 보호

실험 결과

이론적 결과

정리 3 (Kc=1 최적성): (K,U,Kc) 다중 메시지 안전 집계 문제에서 U≤K-1이고 Kc=1일 때, 용량 영역은: R∗={(R1,R2):R1≥1,R2≥1U}\mathcal{R}^* = \{(R_1,R_2) : R_1 \geq 1, R_2 \geq \frac{1}{U}\}

정리 5 (2≤Kc<U 도달 가능성): 2≤Kc<U≤K-1일 때, 속도 튜플 (R1=1,R2=KcU−1)(R_1 = 1, R_2 = \frac{K_c}{U-1})은 도달 가능하다.

정리 6 (역방향 경계): 모든 도달 가능한 속도는 다음을 만족해야 한다: R1≥1,R2≥KcUR_1 \geq 1, R_2 \geq \frac{K_c}{U}

성능 분석

  1. 최적성: Kc=1 경우가 이론적 최적값 달성
  2. 근사 최적성: 2≤Kc<U 경우에서 첫 번째 라운드 속도는 최적이고 두 번째 라운드 속도는 계수 2 내에서 최적: Kc/(U−1)Kc/U=UU−1≤2\frac{K_c/(U-1)}{K_c/U} = \frac{U}{U-1} \leq 2
  3. 기본 방법과의 비교: 직접 반복 방안 대비 새로운 방안은 첫 번째 라운드 속도를 Kc에서 1로 감소시키고, 두 번째 라운드 속도를 Kc/U에서 Kc/(U-1)로 증가

관련 연구

안전 집계

  • 정보 이론적 안전 집계: Zhao와 Sun이 처음 정보 이론적 형식화를 제시하여 용량 영역 {(R1,R2) : R1≥1, R2≥1/U} 달성
  • 실용적 안전 집계: LightSecAgg가 키 생성 과정을 분리하여 필요한 키 수를 크게 감소

프라이빗 정보 검색 및 계산

  • 프라이빗 정보 검색(PIR): 서버가 분산 데이터베이스에서 메시지를 비공개로 검색 가능
  • 프라이빗 계산(PC): PIR 프레임워크를 확장하여 메시지의 선형 계산 포함
  • 대칭 프라이빗 계산: 서버 계산 작업 프라이버시와 사용자 데이터 보안을 동시에 보호

다중 작업 학습

  • 협력 학습: 여러 작업이 정보 및 자원 공유를 통해 협력하여 전체 학습 효율 향상
  • 공통 표현: 작업이 공통 표현, 그래디언트 또는 공유 구성 요소로부터 이득

결론 및 논의

주요 결론

  1. 수요 프라이버시를 갖춘 다중 메시지 안전 집계 문제를 처음으로 형식화
  2. Kc=1에 대해 최적 통신 속도 영역 달성
  3. 2≤Kc<U에 대해 첫 번째 라운드 최적, 두 번째 라운드 근사 최적 성능 달성
  4. 완전한 이론적 분석 프레임워크 제공

한계

  1. 미해결 영역: Kc≥U일 때의 용량 영역 특성화 미해결
  2. 키 크기: 필요한 키 크기 최소화 미최적화
  3. 실용성: 이론적 방안의 실제 시스템 구현 복잡도 높음
  4. 확장성: 비선형 계산 작업으로의 확장성 제한

향후 연구 방향

  1. 용량 영역 완전 특성화: Kc≥U 경우의 최적성 문제 해결
  2. 키 최적화: 필요한 키 크기 최소화로 실용성 향상
  3. 시스템 구현: 실제 배포 가능한 시스템 프로토타입 개발
  4. 비선형 확장: 비선형 계산 작업으로의 확장

심층 평가

장점

  1. 이론적 기여 현저: 안전 집계와 수요 프라이버시를 결합하여 중요한 이론적 공백 해결
  2. 방법 혁신성 강함: 곱셈 암호화와 대칭 프라이빗 계산을 교묘히 결합하여 기술 경로 신규
  3. 이론적 분석 완전: 엄격한 도달 가능성 증명과 역방향 경계 분석 제공
  4. 실제 의의 중대: 연합 학습에서의 중요한 프라이버시 보호 문제 해결

부족점

  1. 적용 범위 제한: 선형 계산 작업만 고려하며 실제 응용에서 비선형 연산 필요 가능
  2. 구현 복잡도 높음: 특히 2≤Kc<U 경우의 대칭 프라이빗 계산 구현 복잡
  3. 매개변수 제약: Kc<U 요구 조건이 일부 응용 시나리오에서 과도히 엄격할 수 있음
  4. 실험 검증 부재: 실제 시스템 구현 및 성능 테스트 부족

영향력

  1. 학술 가치: 안전 다중 당사자 계산 및 연합 학습 분야에 새로운 이론적 프레임워크 제공
  2. 실용 잠재력: 프라이버시 보호 분산 기계 학습을 위한 이론적 기초 제공
  3. 재현성: 이론적 결과는 명확하나 실제 구현에는 상당한 공학 작업 필요

적용 시나리오

  1. 연합 학습: 다중 작업 연합 학습에서의 프라이버시 보호 집계
  2. 분산 통계: 여러 통계량 계산이 필요한 분산 시스템
  3. 프라이버시 보호 분석: 금융, 의료 등 프라이버시 요구가 엄격한 데이터 분석 시나리오

참고 문헌

논문은 다음을 포함한 여러 중요 참고 문헌을 인용:

  • Zhao & Sun의 정보 이론적 안전 집계 연구
  • Sun & Jafar의 프라이빗 정보 검색 및 프라이빗 계산 용량 결과
  • Zhu 등의 대칭 프라이빗 다항식 계산 방안
  • Shannon의 고전 정보 이론 보안 결과

종합 평가: 본 논문은 안전 집계와 프라이버시 보호 계산의 교차 분야에서 중요한 기여를 한 고품질 이론 논문이다. 실용성 측면에서 개선 여지가 있지만, 그 이론적 혁신과 엄격한 분석은 후속 연구의 견고한 기초를 마련한다.