  Label differential privacy (label-DP) is a popular framework for training
private ML models on datasets with public features and sensitive private
labels. Despite its rigorous privacy guarantee, it has been observed that in
practice label-DP does not preclude label inference attacks (LIAs): Models
trained with label-DP can be evaluated on the public training features to
recover, with high accuracy, the very private labels that it was designed to
protect. In this work, we argue that this phenomenon is not paradoxical and
that label-DP is designed to limit the advantage of an LIA adversary compared
to predicting training labels using the Bayes classifier. At label-DP
$\epsilon=0$ this advantage is zero, hence the optimal attack is to predict
according to the Bayes classifier and is independent of the training labels.
Our bound shows the semantic protection conferred by label-DP and gives
guidelines on how to choose $\varepsilon$ to limit the threat of LIAs below a
certain level. Finally, we empirically demonstrate that our result closely
captures the behavior of simulated attacks on both synthetic and real world
datasets.
