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 QuestionsPlease mark one or more for each question.
Is this a proposal for:
[X] A new DP mechanism or component
[ ] Improvement to an existing mechanism or component
[ ] Something else
Is this a feature you plan to implement yourself?
[X] Yes
[ ] No, this is a feature request
[ ] Yes, with help from someone else
Is this an existing DP mechanism or component that has been described in a book or peer-reviewed paper?
[X] Yes: Paper, reviewed and accepted for CCS 2020
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.
Is this a proposal for:
Is this a feature you plan to implement yourself?
Is this an existing DP mechanism or component that has been described in a book or peer-reviewed paper?
We propose to contribute code that:
Additional Questions/Concerns N/A
Additional context Proofs/pseudocode currently under library review.