로컬 차등 프라이버시 환경에서의 희소 숫자 벡터의 견고한 추정

Robust Estimation of Sparse Numerical Vectors under Local Differential Privacy

로컬 차등 프라이버시(LDP) 프로토콜은 공격에 취약합니다. 기존 연구에서는 개별 사용자 항목에 대한 효율적인 방어 전략을 제안했습니다. 그러나 실제로는 사용자가 여러 항목을 보유할 수 있습니다. 다중 항목 사용자에 대한 공격 방어는 더 넓은 출력 공간으로 인해 적이 탐지되지 않고 더욱 강력한 공격을 수행할 수 있기 때문에 어렵습니다. 본 논문에서는 각 사용자가 $m$개의 0이 아닌 좌표를 가진 벡터를 갖는 희소 벡터의 평균 추정 문제를 다룹니다. 우리는 Randomized Projection with Clipping (RPC) 방법을 제안합니다. 먼저, 서버는 각 사용자에게 임의의 이진 벡터를 보냅니다. 사용자는 자신의 로컬 데이터를 해당 벡터에 투영하고 값을 제한하여 공격자의 능력을 억제합니다. 클리핑으로 인한 편향을 처리하기 위해, 우리는 주의 깊은 분석을 통해 편향의 정확한 표현식을 제공하는 수정 방법을 제안합니다. 결과적으로, 더 이상 편향-분산 균형이 필요하지 않으므로, 클리핑 임계값을 더욱 낮춰 출력 공간을 축소하고 견고성을 향상시킬 수 있습니다. 우리는 모든 가능한 공격에 대한 추정 오차에 대한 엄격한 이론적 보장을 제공합니다. 수치 실험 결과, 신뢰할 수 있는 환경에서 새로운 방법은 기존 방법과 비교하거나 더 나은 성능을 달성하며, 이는 제안된 방법 자체가 이미 효율적인 추정기임을 나타냅니다. 비신뢰 환경에서도 제안된 방법은 오염 공격에 대해 훨씬 더 강력한 견고성을 보입니다.

Local differential privacy (LDP) protocols are vulnerable to poisoning attacks. Existing research have proposed efficient defense strategies for single-item users. However, in practice, a user may possess multiple items. The defense against poisoning attacks for multi-item users is challenging, because due to larger output spaces, the adversary can conduct more powerful attacks without being detected. In this paper, we address the robust sparse vector mean estimation problem, in which each user has a vector with $m$ nonzero coordinates. We propose Randomized Projection with Clipping (RPC). Firstly, the server sends a random binary vector to each user. The user then projects its local data on the vector, and clip the value to restrict the attacker's capability. To handle clipping bias, we propose a correction method based on a careful analysis that gives an exact expression of the bias. As a result, bias-variance tradeoff is no longer needed, thus the clipping threshold can be further reduced to shrink the output space and enhance robustness. We provide a rigorous theoretical guarantee of the estimation error under all possible attacks. Numerical experiments show that under trusted environments, our new method achieves comparable or better performance than existing methods, indicating that our method is already an efficient estimator in its own right. Under untrusted environments, our method is also significantly more robust to poisoning attacks.