Equivalence of Non-Perfect Secret Sharing and Symmetric Private Information Retrieval With General Access Structure
Equivalence of Non-Perfect Secret Sharing and Symmetric Private Information Retrieval With General Access Structure
复制标题
非完美秘密共享与通用访问结构的对称隐私信息检索的等价
DOI：
10.1109/jsac.2022.3142375
复制
发表时间：
2022
影响因子：
16.4
通讯作者：
Hayashi Masahito
中科院分区：
文献类型：
--
作者：
Song Seunghoan;Hayashi Masahito
研究了任意响应和合谋模式下的非完美秘密共享（NSS）和对称私有信息检索（SPIR）的等价性。NSS和SPIR定义了一个访问结构，它对应于NSS的授权/禁止集和SPIR的响应/共谋模式。我们证明了NSS和SPIR之间的等价性在以下两个意义上。1)给定任何具有接入结构的SPIR协议，构造具有相同接入结构和相同速率的NSS协议。2)给定任意一个具有接入结构的线性NSS协议，构造一个具有相同接入结构和相同速率的线性SPIR协议。我们证明了第一个关系，即使SPIR协议具有不完美的正确性和保密性。从第一个关系，我们推导出一个上限的SPIR容量为任意响应和共谋模式。对于具有响应和共谋服务器的SPIR的特殊情况，这个上界证明了SPIR容量为。从第二个关系，我们证明了一个SPIR协议存在的任何响应和共谋模式。
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-server SPIR withresponsive andcolluding servers, this upper bound proves that the SPIR capacity is. From the second relation, we prove that a SPIR protocol exists for any response and collusion patterns.