Combinatorial Privacy: Private Multi-Party Bitstream Grand Sum by Hiding in Birkhoff Polytopes

1. 문제 정의 (Problem Statement)

• 목표: $k$ 명의 클라이언트 각각이 길이 $n$ 의 개인 이진 비트스트림 $b_t$ 를 보유하고 있을 때, 서버는 모든 클라이언트의 비트 1 의 총합 $S = \sum_{t=1}^k \sum_{j=1}^n b_{t,j}$ 를 정확히 계산해야 하지만, 개별 클라이언트의 데이터나 부분 합계를 알아서는 안 됩니다.
• 기존 접근법의 한계:
  • MPC (Secure Multi-Party Computation): 회로 복잡도에 비례하여 통신 및 계산 비용이 커져 대규모 $k$ 에 비효율적입니다.
  • Homomorphic Encryption (HE): 공개키 인프라가 필요하며 연산 오버헤드가 큽니다.
  • Differential Privacy (DP): 정확성을 희생하고 노이즈를 추가해야 하므로, 정확한 합계 (Exact Aggregate) 를 얻기 어렵습니다.

2. 방법론 (Methodology)

PolyVeil 은 이중 계층 (Two-Layer) 아키텍처를 기반으로 하며, Birkhoff Polytope(이중 확률 행렬의 볼록 다면체) 의 수학적 성질을 활용합니다.

A. 핵심 아이디어: Birkhoff 인코딩

1. 데이터 인코딩: 각 클라이언트의 비트스트림은 $2n \times 2n$ 크기의 치환 행렬 (Permutation Matrix) $M_t$ 로 인코딩됩니다.
2. 마스크링 (Masking): 클라이언트는 $M_t$ 를 이중 확률 행렬 (Doubly Stochastic Matrix) $D_t$ 로 변환하기 위해 무작위 데코이 치환 행렬 (Decoy Permutation Matrices) 들과 가중치를 혼합합니다.
   • $D_t = \alpha^* M_t + \sum \alpha_{t,i} P_{t,i}$
   • 여기서 $\alpha^*$ 는 신호 강도를 조절하는 상수이며, $P_{t,i}$ 는 무작위 데코이 행렬입니다.
3. 수학적 기반: Birkhoff-von Neumann 정리에 따라, 모든 이중 확률 행렬은 여러 개의 치환 행렬의 볼록 결합으로 표현될 수 있습니다. 이 비유일성 (Non-uniqueness) 이 보안의 핵심 층을 이룹니다.

B. 이중 계층 아키텍처 (Two-Layer Architecture)

초기 프로토콜은 "De-shuffling Attack(순서 복원 공격)"이라는 치명적인 취약점이 발견되어 수정되었습니다. 최종 프로토콜은 다음과 같이 정보를 분리합니다.

1. 레이어 1: 서버의 정보이론적 보안 (Information-Theoretic Security)

   • 역할: 서버는 개별 행렬 $D_t$ 를 보지 않고, 집계된 스칼라 값만 받습니다.
   • 메커니즘: 클라이언트는 $D_t$ 를 통해 추출된 값 $f_t$ 와 데코이 노이즈 $\eta_t$ 를 분리하여 전송합니다. $\eta_t$ 는 신뢰할 수 있는 셔플러 (Shuffler) 를 통해 순서가 섞여 서버로 전달됩니다.
   • 보안: 서버는 최종 집계값 $S$ 만을 계산하며, 입력 데이터가 무엇이든 같은 합계 $S$ 를 가진 경우 서버의 관측치 분포가 완전히 동일합니다 (Perfect Simulation-based Security). 이는 계산 능력과 무관한 무조건적 보안입니다.

2. 레이어 2: 어그리게이터의 계산적 보안 (Computational Security via #P-Hardness)

   • 역할: 별도의 어그리게이터 (Aggregator) 는 각 클라이언트의 행렬 $D_t$ 를 직접 관찰하지만, 노이즈 값 $\eta_t$ 는 알지 못합니다.
   • 공격 시나리오: 어그리게이터가 $D_t$ 에서 원래의 치환 행렬 $M_t$ 를 복원하려 할 때, 이는 무작위 이중 확률 행렬의 밀도 (Density) 를 계산하는 문제와 동치입니다.
   • 보안 증명: 이 밀도 계산 문제는 Permanent(영구식) 계산 문제로 환원되며, 이는 #P-Hard 문제입니다. 따라서 다항 시간 내의 어그리게이터는 $M_t$ 를 효율적으로 복원할 수 없습니다.

C. 압축 변형 (Compressed Variant)

• 클라이언트가 행렬 $D_t$ 대신 스칼라 $f_t$ 만을 전송하는 방식입니다.
• 통신 비용이 $O(n^2)$ 에서 $O(1)$ 로 감소합니다.
• 이 경우 어그리게이터의 관측치가 1 차원 스칼라가 되어 차원 축소 효과가 발생하지만, Birkhoff 구조의 조합적 복잡성은 사라집니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

1. De-shuffling Attack 발견 및 해결:

   • 초기 프로토콜에서는 서버가 $f_t$ 와 섞인 $\eta_t$ 를 비교하여 정수 제약 조건 ($s_t \in \{0, \dots, n\}$) 을 이용해 모든 클라이언트의 데이터를 100% 확률로 복원할 수 있음을 증명했습니다.
   • 이를 해결하기 위해 정보와 노이즈를 분리하는 이중 계층 프로토콜을 설계했습니다.

2. 정확한 집계와 조합적 프라이버시:

   • 기존 DP 와 달리 정확한 (Exact) 합계 결과를 제공합니다.
   • 보안이 수학적 난제 (Number-theoretic hardness) 가 아닌 조합적 구조 (Combinatorial structure, Birkhoff Polytope) 에 기반합니다.

3. 유한 표본 (Finite-Sample) $(\epsilon, \delta)$-DP 분석:

   • 어그리게이터에 대한 명시적인 상수를 가진 $(\epsilon, \delta)$-DP 보장을 증명했습니다.
   • 상반된 결과 (Trade-off):
     • Full Variant (행렬 관측): DP 보장이 성립하려면 신호 대 잡음비 (SNR) 가 극도로 낮아야 하여 신호가 감지 불가능한 상태여야 합니다. 즉, DP 보장은 기술적으로 참이지만 실질적 의미가 없습니다 (Vacuous).
     • Compressed Variant (스칼라 관측): SNR 이 중간 정도일 때 유효한 DP 보장이 가능하지만, 이 경우 Birkhoff 구조의 조합적 보안 (#P-Hardness) 은 사라집니다.
   • 핵심 통찰: "신호가 감지 가능한 영역에서 유효한 DP 보장을 제공하면서 동시에 #P-Hardness 기반의 계산적 보장을 제공하는 단일 프로토콜 변형"은 여전히 해결되지 않은 개방적 문제입니다.

4. 통신 복잡도:

   • 압축 변형에서 $O(k)$ 의 통신 비용으로 확장성을 확보했습니다.

4. 의의 및 결론 (Significance)

• 새로운 패러다임: PolyVeil 은 기존 MPC/HE 의 수학적 난제 기반 보안과 DP 의 통계적 노이즈 기반 보안을 넘어, 행렬 분해의 조합적 복잡성을 보안의 근간으로 삼는 "Combinatorial Privacy"를 제시합니다.
• 보안 계층의 분리: 서버는 정보이론적 보안 (무조건적) 을, 어그리게이터는 계산적 보안 (#P-Hardness) 을 제공받아, 단일 엔티티가 전체 데이터를 복원할 수 없도록 설계되었습니다.
• 한계와 향후 과제: 현재 DP 보장이 유효한 영역 (SNR 낮음) 과 계산적 보안이 유효한 영역 (SNR 중간) 이 분리되어 있습니다. 이 두 영역을 통합하여 신호가 감지 가능한 상태에서도 유효한 DP 보장을 제공하는지 여부가 향후 연구의 핵심 과제로 남았습니다.

요약하자면, PolyVeil 은 Birkhoff Polytope 의 수학적 특성을 활용하여 정확한 집계와 강력한 프라이버시를 동시에 달성하려는 시도이며, 특히 계산적 복잡성과 정보이론적 보안을 결합한 이중 계층 구조를 통해 기존 접근법과 차별화된 새로운 프라이버시 보호 체계를 제시합니다.