Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2101.11194

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

Seunghoan Song, Masahito Hayashi

Published Jan 27, 2021• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2101.11194

Related papers

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.

IEEE Journal on Selected Areas in Communications•Jan 26, 2022•7 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 colluding and unresponsive servers. We prove the equivalence between NSS and SPIR in the following two senses. 1) Given any SPIR protocol, we can construct an NSS protocol. 2) Given any linear NSS protocol, we can construct a SPIR protocol. 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 general access structure. For the special case of n-server SPIR with r responsive and t colluding servers, this upper bound proves that the SPIR capacity is (r-t)/n. From the second relation, we prove that a SPIR protocol exists for any access structure.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•3 citations

The Capacity of Symmetric Private Information Retrieval Under Arbitrary Collusion and Eavesdropping Patterns

Jiale Cheng, Nan Liu, Wei Kang +1 more

We study the symmetric private information retrieval (SPIR) problem under arbitrary collusion and eavesdropping patterns for replicated databases. We find its capacity, which is the same as the capacity of the original SPIR problem with the number of serversNreplaced by a numberF*. The numberF* is the optimal solution to a linear programming problem, and it is a function of the joint pattern, which is the union of the collusion and eavesdropping pattern. This is the first result that shows how two arbitrary patterns collectively affect the capacity of the SPIR problem. We draw the conclusion that for SPIR problems, the collusion and eavesdropping constraints are interchangeable in terms of capacity, i.e., the two patterns play the same role in the SPIR problem and the capacity remains unchanged if we exchange the colluding and eavesdropping patterns. As corollaries of our result, the capacity of the SPIR problem under arbitrary collusion patterns, and the capacity of the PIR problem where each colluding set is included in some eavesdropping set, are also found. Some extensions with restrictions to finite message lengths are provided, and in this case, upper and lower bounds on the capacity are given. The lower bound is described with a solution to an integer linear programming problem.

arXiv:2010.08249•IEEE Transactions on Information Forensics and Security•Jan 1, 2022•29 citations

Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems

Shreya Shrestha Meel, Şennur Ulukuş

We introduce the problem of symmetric private information retrieval (SPIR) on replicated databases modeled by a simple graph. In this model, each vertex corresponds to a server, and a message is replicated on two servers if and only if there is an edge between them. We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph, and we call this as message-specific common randomness. In this setting, we establish a lower bound on the SPIR capacity, i.e., the maximum download rate, for general graphs, by proposing an achievable SPIR scheme. Next, we prove that, for any SPIR scheme to be feasible, the minimum size of message-specific randomness should be equal to the size of a message. Finally, by providing matching upper bounds, we derive the exact SPIR capacity for the class of path and regular graphs.

arXiv:2507.17736•Globecom•Dec 8, 2025•2 citations

Capacity of Quantum Symmetric Private Information Retrieval With Collusion of All But One of Servers

Seunghoan Song, Masahito Hayashi

Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple classical files by downloading quantum systems from non-communicating n servers each of which contains a copy of all files, while the identity of the retrieved file is unknown to each server. Symmetric QPIR (QSPIR) is QPIR in which the user only obtains the queried file but no other information of the other files. In this article, we consider the (n-1)-private QSPIR in which the identity of the retrieved file is secret even if any n-1 servers collude, and derive the QSPIR capacity for this problem which is defined as the maximum ratio of the retrieved file size to the total size of the downloaded quantum systems. For any even number n of servers, we show that the capacity of the (n-1)-private QSPIR is 2/n, when we assume that there are prior entanglements among the servers. We construct an (n-1)-private QSPIR protocol of rate ⌈n/2⌉-1and prove that the capacity is upper bounded by 2/n even if any error probability is allowed. The (n-1)-private QSPIR capacity is strictly greater than the classical counterpart.

arXiv:1903.12556•IEEE Journal on Selected Areas in Information Theory•Jan 26, 2021•19 citations

The Asymptotic Capacity of Byzantine Symmetric Private Information Retrieval and its Consequences

Mohamed W. Nomeir, Alptug Aytekin, Şennur Ulukuş

We consider the problem of finding the asymptotic capacity of symmetric private information retrieval (SPIR) with$B$Byzantine servers. Prior to finding the capacity, a definition for the Byzantine servers is needed since in the literature there are two different definitions. In [1], where it was first defined, the Byzantine servers can send any symbol from the storage, their received queries and some independent random symbols. In [2], Byzantine servers send any random symbol independently of their storage and queries. It is clear that these definitions are not identical, especially when symmetric privacy is required. To that end, we define Byzantine servers, inspired by [1], as the servers that can share everything, before and after the scheme initiation. In this setting, we find an upper bound, for an infinite number of messages case, that should be satisfied for all schemes that protect against this setting and develop a scheme that achieves this upper bound. Hence, we identify the capacity of the problem.

arXiv:2501.17124•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•1 citation
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 n\mathsf{n}n-server SPIR with r\mathsf{r}r responsive and t\mathsf{t}t colluding servers, this upper bound proves that the SPIR capacity is (r−t)/n(\mathsf{r}-\mathsf{t})/\mathsf{n}(r−t)/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 ofn\mathsf {n}n-server SPIR withr\mathsf {r}rresponsive andt\mathsf {t}tcolluding servers, this upper bound proves that the SPIR capacity is(r−t)/n(\mathsf {r}-\mathsf {t})/\mathsf {n}(r−t)/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 colluding and unresponsive servers. We prove the equivalence between NSS and SPIR in the following two senses. 1) Given any SPIR protocol, we can construct an NSS protocol. 2) Given any linear NSS protocol, we can construct a SPIR protocol. 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 general access structure. For the special case of n-server SPIR with r responsive and t colluding servers, this upper bound proves that the SPIR capacity is (r-t)/n. From the second relation, we prove that a SPIR protocol exists for any access structure.
We study the symmetric private information retrieval (SPIR) problem under arbitrary collusion and eavesdropping patterns for replicated databases. We find its capacity, which is the same as the capacity of the original SPIR problem with the number of serversNreplaced by a numberF*. The numberF* is the optimal solution to a linear programming problem, and it is a function of the joint pattern, which is the union of the collusion and eavesdropping pattern. This is the first result that shows how two arbitrary patterns collectively affect the capacity of the SPIR problem. We draw the conclusion that for SPIR problems, the collusion and eavesdropping constraints are interchangeable in terms of capacity, i.e., the two patterns play the same role in the SPIR problem and the capacity remains unchanged if we exchange the colluding and eavesdropping patterns. As corollaries of our result, the capacity of the SPIR problem under arbitrary collusion patterns, and the capacity of the PIR problem where each colluding set is included in some eavesdropping set, are also found. Some extensions with restrictions to finite message lengths are provided, and in this case, upper and lower bounds on the capacity are given. The lower bound is described with a solution to an integer linear programming problem.
We introduce the problem of symmetric private information retrieval (SPIR) on replicated databases modeled by a simple graph. In this model, each vertex corresponds to a server, and a message is replicated on two servers if and only if there is an edge between them. We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph, and we call this as message-specific common randomness. In this setting, we establish a lower bound on the SPIR capacity, i.e., the maximum download rate, for general graphs, by proposing an achievable SPIR scheme. Next, we prove that, for any SPIR scheme to be feasible, the minimum size of message-specific randomness should be equal to the size of a message. Finally, by providing matching upper bounds, we derive the exact SPIR capacity for the class of path and regular graphs.
Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple classical files by downloading quantum systems from non-communicating n servers each of which contains a copy of all files, while the identity of the retrieved file is unknown to each server. Symmetric QPIR (QSPIR) is QPIR in which the user only obtains the queried file but no other information of the other files. In this article, we consider the (n-1)-private QSPIR in which the identity of the retrieved file is secret even if any n-1 servers collude, and derive the QSPIR capacity for this problem which is defined as the maximum ratio of the retrieved file size to the total size of the downloaded quantum systems. For any even number n of servers, we show that the capacity of the (n-1)-private QSPIR is 2/n, when we assume that there are prior entanglements among the servers. We construct an (n-1)-private QSPIR protocol of rate ⌈n/2⌉-1and prove that the capacity is upper bounded by 2/n even if any error probability is allowed. The (n-1)-private QSPIR capacity is strictly greater than the classical counterpart.
We consider the problem of finding the asymptotic capacity of symmetric private information retrieval (SPIR) withBBBByzantine servers. Prior to finding the capacity, a definition for the Byzantine servers is needed since in the literature there are two different definitions. In [1], where it was first defined, the Byzantine servers can send any symbol from the storage, their received queries and some independent random symbols. In [2], Byzantine servers send any random symbol independently of their storage and queries. It is clear that these definitions are not identical, especially when symmetric privacy is required. To that end, we define Byzantine servers, inspired by [1], as the servers that can share everything, before and after the scheme initiation. In this setting, we find an upper bound, for an infinite number of messages case, that should be satisfied for all schemes that protect against this setting and develop a scheme that achieves this upper bound. Hence, we identify the capacity of the problem.