| Paper ID | D2-S7-T4.3 |
| Paper Title |
Equivalence of Non-Perfect Secret Sharing and Symmetric Private Information Retrieval with General Access Structure |
| Authors |
Seunghoan Song, Nagoya University, Japan; Masahito Hayashi, Southern University of Science and Technology, China |
| Session |
D2-S7-T4: Secret Sharing |
| Chaired Session: |
Wednesday, 14 July, 00:00 - 00:20 |
| Engagement Session: |
Wednesday, 14 July, 00:20 - 00:40 |
| Abstract |
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.
|
