  Existing regulations prohibit model developers from accessing protected
attributes (gender, race, etc.), often resulting in fairness assessments on
populations without knowing their protected groups. In such scenarios,
institutions often adopt a separation between the model developers (who train
models with no access to the protected attributes) and a compliance team (who
may have access to the entire dataset for auditing purposes). However, the
model developers might be allowed to test their models for bias by querying the
compliance team for group fairness metrics. In this paper, we first demonstrate
that simply querying for fairness metrics, such as statistical parity and
equalized odds can leak the protected attributes of individuals to the model
developers. We demonstrate that there always exist strategies by which the
model developers can identify the protected attribute of a targeted individual
in the test dataset from just a single query. In particular, we show that one
can reconstruct the protected attributes of all the individuals from O(Nk \log(
n /Nk)) queries when Nk<<n using techniques from compressed sensing (n: size of
the test dataset, Nk: size of smallest group). Our results pose an interesting
debate in algorithmic fairness: should querying for fairness metrics be viewed
as a neutral-valued solution to ensure compliance with regulations? Or, does it
constitute a violation of regulations and privacy if the number of queries
answered is enough for the model developers to identify the protected
attributes of specific individuals? To address this supposed violation, we also
propose Attribute-Conceal, a novel technique that achieves differential privacy
by calibrating noise to the smooth sensitivity of our bias query, outperforming
naive techniques such as the Laplace mechanism. We also include experimental
results on the Adult dataset and synthetic data.
