English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the federated frequency estimation problem, where each user holdsa private item $X_i$ from a size-$d$ domain and a server aims to estimate theempirical frequency (i.e., histogram) of $n$ items with $n \ll d$. Without anysecurity and privacy considerations, each user can communicate its item to theserver by using $\log d$ bits. A naive application of secure aggregationprotocols would, however, require $d\log n$ bits per user. Can we reduce thecommunication needed for secure aggregation, and does security come with afundamental cost in communication?  In this paper, we develop an information-theoretic model for secureaggregation that allows us to characterize the fundamental cost of security andprivacy in terms of communication. We show that with security (and withoutprivacy) $\Omega\left( n \log d \right)$ bits per user are necessary andsufficient to allow the server to compute the frequency distribution. This issignificantly smaller than the $d\log n$ bits per user needed by the naivescheme, but significantly higher than the $\log d$ bits per user needed withoutsecurity. To achieve differential privacy, we construct a linear scheme basedon a noisy sketch which locally perturbs the data and does not require atrusted server (a.k.a. distributed differential privacy). We analyze thisscheme under $\ell_2$ and $\ell_\infty$ loss. By using ourinformation-theoretic framework, we show that the scheme achieves the optimalaccuracy-privacy trade-off with optimal communication cost, while matching theperformance in the centralized case where data is stored in the central server.

The communication cost of security and privacy in federated frequency estimation