Converse Bounds for Sun-Jafar-type Weak Private Information Retrieval
For researchers in information-theoretic privacy, this paper establishes optimality bounds for a class of WPIR schemes, though the results are incremental and constrained to specific parameter regimes.
This work proves class-wise optimality of rate-privacy trade-offs for Sun-Jafar-type weak private information retrieval schemes in non-colluding replicated settings, and for Banawan-Ulukus-type MDS-WPIR and Sun-Jafar-type T-colluding WPIR under threshold constraints. It also provides counterexamples showing higher rates are achievable when constraints are violated.
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.