Categorical values and the Exponential Mechanism

[SSoelvsten]

Zhang and Kifer [ZK17] mention briefly the ability to extend the notion of distance to boolean values. Based on the PrivBernoulli algorithm [ZK17, Figure 13] they first sample η from a Uniform distribution in [0,1] and then let b be true if η > t ∈ [0,1] and false otherwise. This idea is easily extensible to categorical values of more than two values, such as enums, by use of the more general Exponential Mechanism [ZK17].

They provide a differential privacy type-checking rule and transformation for sampling from a uniform distribution, which should be possible to directly incorporate into MLightDP. One may further abstract this from the user to allow one to sample a random boolean that is true with probability p, such that they only need to write

let b := RandBool(p)

which in the refinement step is translated into

let eta = Uniform(0,1)
let b = eta <= p ? true : false

and finally in the differential privacy type checking step is proven differentiably private according to the rule as provided by Zhang and Kifer [ZK17].