본 논문은 국소적 차등 프라이버시(LDP) 빈도 추정을 위한 새로운 알고리즘인 ModularSubsetSelection(MSS)을 제시합니다. 크기 $k$의 전체 집합과 $n$명의 사용자를 고려할 때, MSS는 $\ell$개의 쌍별 공소수 모듈 $m_0, \ldots, m_{\ell-1}$을 사용하여 각 입력을 잔여 숫자 시스템(RNS)을 통해 인코딩합니다. 그런 다음, 통계적으로 최적의 SubsetSelection(SS) (Wang et al. 2016)을 사용하여 임의로 선택된 인덱스 $j \in [\ell]$와 교란된 잔차를 보고합니다. 이 설계는 표준 SS가 필요로 하는 $\Theta(\omega \log_2(k/\omega))$ 비트의 사용자 통신 비용을 $\lceil \log_2 \ell \rceil + \lceil \log_2 m_j \rceil$ 비트로 줄입니다 (여기서 $m_j < k$). 서버 측 디코딩은 $\Theta(n + r k \ell)$ 시간 안에 실행됩니다. 여기서 $r$은 LSMR (Fong and Saunders 2011) 반복 횟수입니다. MSS는 PGR(Feldman et al. 2022)과 같은 최첨단 프로토콜의 최악의 경우 MSE 내에서 상수 인자를 달성합니다. MSS는 SS, PGR, RAPPOR (Erlingsson, Pihur, and Korolova 2014)의 추정 정확도와 일치하며 PGR보다 빠른 디코딩과 SS보다 짧은 사용자 메시지를 제공합니다. 마지막으로, MSS는 여러 모듈에서 샘플링하고 단일 교란된 잔차만 보고함으로써 모든 평가된 LDP 프로토콜 중에서 가장 낮은 재구성 공격 성공률을 달성합니다.
