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 study the problem of private set intersection (PSI). In this problem, there are two entities <inline-formula> <tex-math notation="LaTeX">$E_{i}$ </tex-math></inline-formula>, for <inline-formula> <tex-math notation="LaTeX">$i=1, 2$ </tex-math></inline-formula>, each storing a set <inline-formula> <tex-math notation="LaTeX">$\mathcal {P}_{i}$ </tex-math></inline-formula>, whose elements are picked from a finite set <inline-formula> <tex-math notation="LaTeX">$\mathbb {S}_{K}$ </tex-math></inline-formula>, on <inline-formula> <tex-math notation="LaTeX">$N_{i}$ </tex-math></inline-formula> replicated and non-colluding databases. It is required to determine the set intersection <inline-formula> <tex-math notation="LaTeX">${\mathcal {P}}_{1} \cap {\mathcal {P}} _{2}$ </tex-math></inline-formula> without leaking any information about the remaining elements to the other entity, and to do this with the least amount of downloaded bits. We first show that the PSI problem can be recast as a multi-message symmetric private information retrieval (MM-SPIR) problem with certain added restrictions. Next, as a stand-alone result, we derive the information-theoretic sum capacity of MM-SPIR, <inline-formula> <tex-math notation="LaTeX">$C_{MM-SPIR}$ </tex-math></inline-formula>. We show that with <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> messages, <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> databases, and a given size of the desired message set <inline-formula> <tex-math notation="LaTeX">$P$ </tex-math></inline-formula>, the exact capacity of MM-SPIR is <inline-formula> <tex-math notation="LaTeX">$C_{MM-SPIR} = 1 - \frac {1}{N}$ </tex-math></inline-formula> when <inline-formula> <tex-math notation="LaTeX">$P \leq K-1$ </tex-math></inline-formula>, provided that the entropy of the common randomness <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula> satisfies <inline-formula> <tex-math notation="LaTeX">$H(S) \geq \frac {P}{N-1}$ </tex-math></inline-formula> per desired symbol. When <inline-formula> <tex-math notation="LaTeX">$P = K$ </tex-math></inline-formula>, the MM-SPIR capacity is trivially 1 without the need for any common randomness <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula>. This result implies that there is no gain for MM-SPIR over successive single-message SPIR (SM-SPIR). For the MM-SPIR problem, we present a novel capacity-achieving scheme which builds seamlessly over the near-optimal scheme of Banawan-Ulukus originally proposed for the multi-message PIR (MM-PIR) problem without any database privacy constraints. Surprisingly, our scheme here is exactly optimal for the MM-SPIR problem for any <inline-formula> <tex-math notation="LaTeX">$P$ </tex-math></inline-formula>, in contrast to the scheme for the MM-PIR problem, which was proved only to be near-optimal. Our scheme is an alternative to the successive usage of the SM-SPIR scheme of Sun-Jafar. Based on this capacity result for the MM-SPIR problem, and after addressing the added requirements in its conversion to the PSI problem, we show that the optimal download cost for the PSI problem is given by <inline-formula> <tex-math notation="LaTeX">$\min \left \{{\left \lceil{ \frac {P_{1} N_{2}}{N_{2}-1}}\right \rceil, \left \lceil{ \frac {P_{2} N_{1}}{N_{1}-1}}\right \rceil }\right \}$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$P_{i}$ </tex-math></inline-formula> is the cardinality of set <inline-formula> <tex-math notation="LaTeX">${\mathcal {P}}_{i}$ </tex-math></inline-formula>.

Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective