[Feature Proposal] Base-2 Exponential Mechanism

[cilvento]

Contributors
Christina Ilvento
OpenDP contacts/consulted with: Michael Shoemate, Christian Covington

Describe the proposed feature
The base-2 exponential mechanism is an exact implementation of the exponential mechanism that prevents floating-point or inexact arithmetic based attacks. The mechanism works by re-casting privacy in terms of 2^eta rather than e^epsilon, and choosing eta so that 2^eta can be computed exactly. Non-integer utility functions are handled via randomized rounding. Sampling is done using a normalized sampling without division method. Paper

Are there alternatives to this feature already included in the library?
There is an existing exponential mechanism, but it may be vulnerable to the attacks laid out in the paper (although I have not explicitly verified the attacks on this implementation). The existing implementation also doesn't satisfy the exact distribution semantics required by some use-cases (e.g., integer partitions).

OpenDP Fit
Exponential mechanism is a core DP mechanism and used in many applications. An exact implementation specifically enables use-cases where exact sampling distribution is critical for the proof of privacy.

Detailed Questions
Please mark one or more for each question.

1. Is this a proposal for:

   • A new DP mechanism or component
   • Improvement to an existing mechanism or component
   • Something else

2. Is this a feature you plan to implement yourself?

   • Yes
   • No, this is a feature request
   • Yes, with help from someone else

3. Is this an existing DP mechanism or component that has been described in a book or peer-reviewed paper?

   • Yes: Paper, reviewed and accepted for CCS 2020
   • No
   • There is a paper/book currently under review

4. We propose to contribute code that:

   • Already exists in a public github repo: Link
   • Exists, but is private
   • Is work in progress
   • Does not yet exist
   • We do not plan to implement, this is a feature request

Additional Questions/Concerns
N/A

Additional context
Proofs/pseudocode currently under library review.