All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD2-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.