We study the equivalence between non-perfect secret sharing (NSS) and symmetric private information retrieval (SPIR) with arbitrary response and collusion patterns. NSS and SPIR are defined with an access structure, which corresponds to the authorized/forbidden sets for NSS and the response/collusion patterns for SPIR. We prove the equivalence between NSS and SPIR in the following two senses. 1) Given any SPIR protocol with an access structure, an NSS protocol is constructed with the same access structure and the same rate. 2) Given any linear NSS protocol with an access structure, a linear SPIR protocol is constructed with the same access structure and the same rate. We prove the first relation even if the SPIR protocol has imperfect correctness and secrecy. From the first relation, we derive an upper bound of the SPIR capacity for arbitrary response and collusion patterns. For the special case of $\mathsf {n}$ -server SPIR with $\mathsf {r}$ responsive and $\mathsf {t}$ colluding servers, this upper bound proves that the SPIR capacity is $(\mathsf {r}-\mathsf {t})/\mathsf {n}$ . From the second relation, we prove that a SPIR protocol exists for any response and collusion patterns.We study the equivalence between non-perfect secret sharing (NSS) and symmetric private information retrieval (SPIR) with arbitrary response and collusion patterns. NSS and SPIR are defined with an access structure, which corresponds to the authorized/forbidden sets for NSS and the response/collusion patterns for SPIR. We prove the equivalence between NSS and SPIR in the following two senses. 1) Given any SPIR protocol with an access structure, an NSS protocol is constructed with the same access structure and the same rate. 2) Given any linear NSS protocol with an access structure, a linear SPIR protocol is constructed with the same access structure and the same rate. We prove the first relation even if the SPIR protocol has imperfect correctness and secrecy. From the first relation, we derive an upper bound of the SPIR capacity for arbitrary response and collusion patterns. For the special case of$\mathsf {n}$-server SPIR with$\mathsf {r}$responsive and$\mathsf {t}$colluding servers, this upper bound proves that the SPIR capacity is$(\mathsf {r}-\mathsf {t})/\mathsf {n}$. From the second relation, we prove that a SPIR protocol exists for any response and collusion patterns.

IEEE Journal on Selected Areas in CommunicationsJan 26, 20227 citations

Lattice-based access authentication scheme for quantum communication networks

Min Wang, Gui‐Lu Long

Science China Information SciencesNov 7, 202417 citations

Equivalence of Non-Perfect Secret Sharing and Symmetric Private Information Retrieval with General Access Structure

Seunghoan Song, Masahito Hayashi

We study the equivalence between non-perfect secret sharing (NSS) and symmetric private information retrieval (SPIR) with arbitrary response and collusion patterns. NSS and SPIR are defined with an access structure, which corresponds to the authorized/forbidden sets for NSS and the response/collusion patterns for SPIR. We prove the equivalence between NSS and SPIR in the following two senses. 1) Given any SPIR protocol with an access structure, an NSS protocol is constructed with the same access structure and the same rate. 2) Given any linear NSS protocol with an access structure, a linear SPIR protocol is constructed with the same access structure and the same rate. We prove the first relation even if the SPIR protocol has imperfect correctness and secrecy. From the first relation, we derive an upper bound of the SPIR capacity for arbitrary response and collusion patterns. For the special case of $\mathsf{n}$ -server SPIR with $\mathsf{r}$ responsive and $\mathsf{t}$ colluding servers, this upper bound proves that the SPIR capacity is $(\mathsf{r}-\mathsf{t})/\mathsf{n}$ . From the second relation, we prove that a SPIR protocol exists for any response and collusion patterns.We study the equivalence between non-perfect secret sharing (NSS) and symmetric private information retrieval (SPIR) with arbitrary response and collusion patterns. NSS and SPIR are defined with an access structure, which corresponds to the authorized/forbidden sets for NSS and the response/collusion patterns for SPIR. We prove the equivalence between NSS and SPIR in the following two senses. 1) Given any SPIR protocol with an access structure, an NSS protocol is constructed with the same access structure and the same rate. 2) Given any linear NSS protocol with an access structure, a linear SPIR protocol is constructed with the same access structure and the same rate. We prove the first relation even if the SPIR protocol has imperfect correctness and secrecy. From the first relation, we derive an upper bound of the SPIR capacity for arbitrary response and collusion patterns. For the special case of $\mathsf{n}$-server SPIR with $\mathsf{r}$ responsive and $\mathsf{t}$ colluding servers, this upper bound proves that the SPIR capacity is $(\mathsf{r}-\mathsf{t})/\mathsf{n}$. From the second relation, we prove that a SPIR protocol exists for any response and collusion patterns.

arXiv:2101.11194Jan 27, 20211 citation

Quantum symmetrically-private information retrieval

Iordanis Kerenidis, Ronald de Wolf

arXiv:quant-ph/0307076Information Processing LettersMar 12, 200461 citations

\mathsf {n}

-server SPIR with

\mathsf {r}

responsive and

\mathsf {t}

colluding servers, this upper bound proves that the SPIR capacity is

(\mathsf {r}-\mathsf {t})/\mathsf {n}

. From the second relation, we prove that a SPIR protocol exists for any response and collusion patterns.

\mathsf{n}

-server SPIR with

\mathsf{r}

responsive and

\mathsf{t}

colluding servers, this upper bound proves that the SPIR capacity is

(\mathsf{r}-\mathsf{t})/\mathsf{n}

. From the second relation, we prove that a SPIR protocol exists for any response and collusion patterns.