Improved Achievable Rate for Single-Server SPIR over Binary Erasure Channels
Amirhossein Shekofteh, Rémi A. Chou
Abstract
In 1-out-of-D Symmetric Private Information Retrieval (SPIR) protocols, the client privately selects and retrieves one of the D files stored on a server, learns nothing about the remaining D − 1 files, and keeps its choice hidden from the server. We propose an achievable rate scheme for 1-out-of- D SPIR in a single-server setting over a binary erasure channel (BEC) with parameter ϵ, where the server controls the BEC input and the client observes the output. Existing 1-out-of-D SPIR protocols over BEC that build on repeated 1-out-of-2 primitives define the achievable rate as the number of bits transmitted per channel use. We propose a 1-out-of-D SPIR scheme over the BEC by repeating a novel 1-out-of-M SPIR scheme where [Editor’s note: see paper for mathematical equation]. Our derived achievable rate surpasses existing rates for ϵ ∈ [1/2, 1], and achieves the SPIR capacity for D = 2, and for D > 2 when [Editor’s note: see paper for mathematical equation].