arXiv cs.AI

残余数システムによるプライベート周波数推定

Private Frequency Estimation Via Residue Number Systems

http://arxiv.org/abs/2511.11569v1


本稿では、地元で異なるプライベート(LDP)周波数推定のための新しいアルゴリズム「ModularSubsetSelection(MSS)」を提案します。ユーザー数がn、ユニバースのサイズがkの時、MSSは$ε$-LDP機構を使用し、各入力をℓ個の互いに素な剰余数系(RNS)を通じて符号化します。ユーザーは、ランダムに選ばれたインデックスjと、そのインデックスに対する乱数後の剰余を送信します。この設計により、ユーザー通信コストは従来のアルゴリズムに比べて大幅に削減され、デコーディング時間も効率的になります。MSSは、最悪の場合でも他の最先端プロトコルと同等の正確性を持ちながら、代数的前提条件や動的計画法のデコーダを回避できます。また、複数のモジュリからサンプリングし、一つの剰余のみを報告することで、再構成攻撃の成功率が最も低いことも示されています。