  Data anonymization is an approach to privacy-preserving data release aimed at
preventing participants reidentification, and it is an important alternative to
differential privacy in applications that cannot tolerate noisy data. Existing
algorithms for enforcing $k$-anonymity in the released data assume that the
curator performing the anonymization has complete access to the original data.
Reasons for limiting this access range from undesirability to complete
infeasibility. This paper explores ideas -- objectives, metrics, protocols, and
extensions -- for reducing the trust that must be placed in the curator, while
still maintaining a statistical notion of $k$-anonymity. We suggest trust
(amount of information provided to the curator) and privacy (anonymity of the
participants) as the primary objectives of such a framework. We describe a
class of protocols aimed at achieving these goals, proposing new metrics of
privacy in the process, and proving related bounds. We conclude by discussing a
natural extension of this work that completely removes the need for a central
curator.
