Converse Bounds for Sun-Jafar-type Weak Private Information Retrieval

Building on the well-established capacity-achieving schemes of Sun-Jafar (for replicated storage) and the closely related scheme of Banawan-Ulukus (for MDS-coded setting), a recent work by Anand et al. proposed new classes of weak private information retrieval (WPIR) schemes for the collusion-free (replication and MDS-coded) setting, as well as for the $T$-colluding scenario.

In their work, Anand et al. characterized the expressions for the rate-privacy trade-offs for these classes of WPIR schemes, under the mutual information leakage and maximal leakage metrics.

Explicit achievable trade-offs for the same were also presented, which were shown to be competitive or better than prior WPIR schemes.

However, the class-wise optimality of the reported trade-offs was unknown.

In this work, we show that the explicit rate-privacy trade-offs reported for the Sun-Jafar-type schemes by Anand et al. are class-wise optimal for the non-colluding and replicated setting.

Furthermore, we prove the class-wise optimality for Banawan-Ulukus-type MDS-WPIR and Sun-Jafar-type $T$-colluding WPIR schemes, under threshold-constraints on the system parameters.

When these threshold-constraints do not hold, we present counter-examples which show that even higher rates than those reported before can be achieved.