  In this work, a flexible and robust private information retrieval (PIR)
scheme based on binary non-maximum distance separable (non-MDS) codes is
considered. This combines previous works on PIR schemes based on transitive
non-MDS codes on one hand, and PIR from MDS-coded Byzantine and non-responsive
servers on the other hand. More specifically, a PIR scheme employing binary
Reed-Muller (RM) codes tolerant to colluding, Byzantine, and non-responsive
servers is constructed, and bounds for the achievable rates are derived under
certain conditions. The construction of such schemes turns out to be much more
involved than for MDS codes. Namely, the binary query vectors have to be
selected with great care to hit the desired information sets, which is
technically challenging as will be shown.
