Title: Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.,
Abstract: A $(K, N, T, K_c)$ instance of the MDS-TPIR problem is comprised of $K$
messages and $N$ distributed servers. Each message is separately encoded
through a $(K_c, N)$ MDS storage code. A user wishes to retrieve one message,
as efficiently as possible, while revealing no information about the desired
message index to any colluding set of up to $T$ servers. The fundamental limit
on the efficiency of retrieval, i.e., the capacity of MDS-TPIR is known only at
the extremes where either $T$ or $K_c$ belongs to $\{1,N\}$. The focus of this
work is a recent conjecture by Freij-Hollanti, Gnilke, Hollanti and Karpuk
which offers a general capacity expression for MDS-TPIR. We prove that the
conjecture is false by presenting as a counterexample a PIR scheme for the
setting $(K, N, T, K_c) = (2,4,2,2)$, which achieves the rate $3/5$, exceeding
the conjectured capacity, $4/7$. Insights from the counterexample lead us to
capacity characterizations for various instances of MDS-TPIR including all
cases with $(K, N, T, K_c) = (2,N,T,N-1)$, where $N$ and $T$ can be arbitrary.