  Machine learning classifiers rely on loss functions for performance
evaluation, often on a private (hidden) dataset. In a recent line of research,
label inference was introduced as the problem of reconstructing the ground
truth labels of this private dataset from just the (possibly perturbed)
cross-entropy loss function values evaluated at chosen prediction vectors
(without any other access to the hidden dataset). In this paper, we formally
study the necessary and sufficient conditions under which label inference is
possible from \emph{any} (noisy) loss function value. Using tools from
analytical number theory, we show that a broad class of commonly used loss
functions, including general Bregman divergence-based losses and multiclass
cross-entropy with common activation functions like sigmoid and softmax, it is
possible to design label inference attacks that succeed even for arbitrary
noise levels and using only a single query from the adversary. We formally
study the computational complexity of label inference and show that while in
general, designing adversarial prediction vectors for these attacks is
co-NP-hard, once we have these vectors, the attacks can also be carried out
through a lightweight augmentation to any neural network model, making them
look benign and hard to detect. The observations in this paper provide a deeper
understanding of the vulnerabilities inherent in modern machine learning and
could be used for designing future trustworthy ML.
