# Symmetric Private Information Retrieval with User-Side Common Randomness

arXiv: https://arxiv.org/abs/2105.05807 · HTML: https://mlsanity.com/paper/2105.05807/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2021.

## Built on by (most cited first, 1 of 1)

- [Federated One-Shot Learning with Data Privacy and Objective-Hiding](https://mlsanity.com/paper/2504.21182/) (2025)

## Abstract (arXiv)

We consider the problem of symmetric private information retrieval (SPIR) with user-side common randomness. In SPIR, a user retrieves a message out of K messages from N non-colluding and replicated databases in such a way that no single database knows the retrieved message index (user privacy), and the user gets to know nothing further than the retrieved message (database privacy). SPIR has a capacity smaller than the PIR capacity which requires only user privacy, is infeasible in the case of a single database, and requires shared common randomness among the databases. We introduce a new variant of SPIR where the user is provided with a random subset of the shared database common randomness, which is unknown to the databases. We determine the exact capacity region of the triple (d, ρS, ρU), where d is the download cost, ρS is the amount of shared database (server) common randomness, and ρU is the amount of available user-side common randomness. We show that with a suitable amount of ρU, this new SPIR achieves the capacity of conventional PIR. As a corollary, single-database SPIR becomes feasible. Further, the presence of user-side ρU reduces the amount of required server-side ρS.