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. From this equivalence relation, we prove that the capacity of $\mathsf{n}$-server SPIR with $\mathsf{r}$ responsive servers and $\mathsf{r}$ colluding servers is $(\mathsf{r}-\mathsf{t})/\mathsf{n}$.


翻译:我们研究非完美秘密共享和对称私人信息检索(SPIR)与串通服务器和不反应服务器的对称私人信息检索(SPIR)之间的等同性。我们在以下两个意义上证明了NSS和SPIR之间的等同性。 (1)根据任何SPIR协议,我们可以建立一个NSS协议。(2)根据任何线性NSS协议,我们可以建立一个SPIR协议。从这种等同关系中,我们证明$\mathsf{n}$-服务器与$\mathsf{r}反应服务器和$\mathsf{r}美元串通服务器的容量是$(mathsf{r}-\mathsf{t}/\mathsfsf{t}/\mathsfsf{n}。

0
下载
关闭预览

相关内容

《计算机信息》杂志发表高质量的论文,扩大了运筹学和计算的范围,寻求有关理论、方法、实验、系统和应用方面的原创研究论文、新颖的调查和教程论文,以及描述新的和有用的软件工具的论文。官网链接:https://pubsonline.informs.org/journal/ijoc
因果图,Causal Graphs,52页ppt
专知会员服务
243+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
57+阅读 · 2019年10月17日
已删除
将门创投
4+阅读 · 2020年1月6日
Arxiv
0+阅读 · 2021年3月22日
Arxiv
0+阅读 · 2021年3月20日
Arxiv
0+阅读 · 2021年3月18日
Arxiv
0+阅读 · 2021年3月18日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关VIP内容
因果图,Causal Graphs,52页ppt
专知会员服务
243+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
57+阅读 · 2019年10月17日
相关资讯
已删除
将门创投
4+阅读 · 2020年1月6日
Top
微信扫码咨询专知VIP会员