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:2509.13684 · Lecture notes in computer science

Publicly Verifiable Private Information Retrieval Protocols Based on Function Secret Sharing

Lin Zhu, Lingwei Kong, Xin Ning, Xiaoyang Qu, J M Wang

Published Jan 1, 2026• 0 citations
arXivHTMLPDF
DOI
10.1007/978-981-95-6209-1_4

Related papers

Verifiable Single-Server Private Information Retrieval

Xingfeng Wang, Liang Zhao

Lecture notes in computer science•Jan 1, 2018•12 citations

Σ-private private information retrieval protocols

Zhang Zi

We pose the definition ofΣ-private private information retrieval(PIR)protocol,and then construct a Σ-private PIR protocol based on verifiable secret sharing(VSS)scheme on general access structure.We also construct an efficient robustΣ-private PIR protocol based on robust multiplication protocol and the database is also secure.The corresponding communication complexity is dependent on the size of the access structure and is efficient for minority of servers.

Journal of the Graduate School of the Chinese Academy of Sciences•Jan 1, 2011•0 citations

Protecting Data Privacy in Private Information Retrieval Schemes

Yael Gertner, Yuval Ishai, Eyal Kushilevitz Z +1 more

Journal of Computer and System Sciences•Jun 1, 2000•214 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

Verifiable Secret Sharing as Secure Computation

Rosario Gennaro, Silvio M. Micali

Lecture notes in computer science•Jan 1, 1995•34 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.

IEEE Journal on Selected Areas in Communications•Jan 26, 2022•7 citations
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 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.