I. Introduction
Secret sharing (SS) and private information retrieval (PIR) are two extensively studied cryptographic protocols. SS [2], [3] considers the problem in which a dealer encodes a secret into n shares so that some subsets of shares can reconstruct the secret but the other subsets have no information of the secret. PIR [4] considers the problem in which a user retrieves one of the multiple files from server(s) without revealing which file is retrieved. Since PIR with one server has no efficient solution [4], it has been extensively studied with multiple noncommunicating servers, and thus, in the following, we simply denote multi-server PIR by PIR. SS and PIR have a similar structure because the secrecy of both protocols is obtained by partitioning the confidential information and restricting the access to the partitioned information. On the other hand, the two protocols have a different structure because the secret of SS is both the confidential and targeted information but the targeted file of PIR is not confidential. From the similarity, there have been several studies to construct PIR from secret sharing [5]–[8]. However, the relationship between these two protocols has not been exhaustively discussed.