prio/
dp.rs

1// SPDX-License-Identifier: MPL-2.0
2
3//! Differential privacy (DP) primitives.
4//!
5//! There are three main traits defined in this module:
6//!
7//!  - `DifferentialPrivacyBudget`: Implementors should be types of DP-budgets,
8//!    i.e., methods to measure the amount of privacy provided by DP-mechanisms.
9//!    Examples: zCDP, ApproximateDP (Epsilon-Delta), PureDP
10//!
11//!  - `DifferentialPrivacyDistribution`: Distribution from which noise is sampled.
12//!    Examples: DiscreteGaussian, DiscreteLaplace
13//!
14//!  - `DifferentialPrivacyStrategy`: This is a combination of choices for budget and distribution.
15//!    Examples: zCDP-DiscreteGaussian, EpsilonDelta-DiscreteGaussian
16//!
17use num_bigint::{BigInt, BigUint, TryFromBigIntError};
18use num_rational::{BigRational, Ratio};
19use serde::{Deserialize, Serialize};
20
21/// Errors propagated by methods in this module.
22#[derive(Debug, thiserror::Error)]
23#[non_exhaustive]
24pub enum DpError {
25    /// Tried to use an invalid float as privacy parameter.
26    #[error(
27        "DP error: input value was not a valid privacy parameter. \
28             It should to be a non-negative, finite float."
29    )]
30    InvalidFloat,
31
32    /// Tried to construct a rational number with zero denominator.
33    #[error("DP error: input denominator was zero.")]
34    ZeroDenominator,
35
36    /// Tried to convert BigInt into something incompatible.
37    #[error("DP error: {0}")]
38    BigIntConversion(#[from] TryFromBigIntError<BigInt>),
39
40    /// Invalid parameter value.
41    #[error("invalid parameter: {0}")]
42    InvalidParameter(String),
43}
44
45/// Positive arbitrary precision rational number to represent DP and noise distribution parameters in
46/// protocol messages and manipulate them without rounding errors.
47#[derive(Clone, Debug)]
48pub struct Rational(Ratio<BigUint>);
49
50impl Rational {
51    /// Construct a [`Rational`] number from numerator `n` and denominator `d`. Errors if denominator is zero.
52    pub fn from_unsigned<T>(n: T, d: T) -> Result<Self, DpError>
53    where
54        T: Into<u128>,
55    {
56        // we don't want to expose BigUint in the public api, hence the Into<u128> bound
57        let d = d.into();
58        if d == 0 {
59            Err(DpError::ZeroDenominator)
60        } else {
61            Ok(Rational(Ratio::<BigUint>::new(n.into().into(), d.into())))
62        }
63    }
64}
65
66impl TryFrom<f32> for Rational {
67    type Error = DpError;
68    /// Constructs a `Rational` from a given `f32` value.
69    ///
70    /// The special float values (NaN, positive and negative infinity) result in
71    /// an error. All other values are represented exactly, without rounding errors.
72    fn try_from(value: f32) -> Result<Self, DpError> {
73        match BigRational::from_float(value) {
74            Some(y) => Ok(Rational(Ratio::<BigUint>::new(
75                y.numer().clone().try_into()?,
76                y.denom().clone().try_into()?,
77            ))),
78            None => Err(DpError::InvalidFloat)?,
79        }
80    }
81}
82
83/// Marker trait for differential privacy budgets (regardless of the specific accounting method).
84pub trait DifferentialPrivacyBudget {}
85
86/// Marker trait for differential privacy scalar noise distributions.
87pub trait DifferentialPrivacyDistribution {}
88
89/// Zero-concentrated differential privacy (ZCDP) budget as defined in [[BS16]].
90///
91/// [BS16]: https://arxiv.org/pdf/1605.02065.pdf
92#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize, Ord, PartialOrd)]
93pub struct ZCdpBudget {
94    epsilon: Ratio<BigUint>,
95}
96
97impl ZCdpBudget {
98    /// Create a budget for parameter `epsilon`, using the notation from [[CKS20]] where `rho = (epsilon**2)/2`
99    /// for a `rho`-ZCDP budget.
100    ///
101    /// [CKS20]: https://arxiv.org/pdf/2004.00010.pdf
102    // TODO(#1095): This should be fallible, and it should return an error if epsilon is zero.
103    pub fn new(epsilon: Rational) -> Self {
104        Self { epsilon: epsilon.0 }
105    }
106}
107
108impl DifferentialPrivacyBudget for ZCdpBudget {}
109
110/// Pure differential privacy budget. (&epsilon;-DP or (&epsilon;, 0)-DP)
111#[derive(Clone, Debug, Eq, PartialEq, Serialize, Ord, PartialOrd)]
112pub struct PureDpBudget {
113    epsilon: Ratio<BigUint>,
114}
115
116impl PureDpBudget {
117    /// Create a budget for parameter `epsilon`.
118    pub fn new(epsilon: Rational) -> Result<Self, DpError> {
119        if epsilon.0.numer() == &BigUint::ZERO {
120            return Err(DpError::InvalidParameter("epsilon cannot be zero".into()));
121        }
122        Ok(Self { epsilon: epsilon.0 })
123    }
124}
125
126impl DifferentialPrivacyBudget for PureDpBudget {}
127
128/// This module encapsulates a deserialization helper struct. It is needed so we can wrap its
129/// derived `Deserialize` implementation in a customized `Deserialize` implementation, which makes
130/// use of the budget's constructor to enforce input validation invariants.
131mod budget_serde {
132    use num_bigint::BigUint;
133    use num_rational::Ratio;
134    use serde::{de, Deserialize};
135
136    #[derive(Deserialize)]
137    pub struct PureDpBudget {
138        epsilon: Ratio<BigUint>,
139    }
140
141    impl<'de> Deserialize<'de> for super::PureDpBudget {
142        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
143        where
144            D: serde::Deserializer<'de>,
145        {
146            let helper = PureDpBudget::deserialize(deserializer)?;
147            super::PureDpBudget::new(super::Rational(helper.epsilon))
148                .map_err(|_| de::Error::custom("epsilon cannot be zero"))
149        }
150    }
151}
152
153/// Strategy to make aggregate results differentially private, e.g. by adding noise from a specific
154/// type of distribution instantiated with a given DP budget.
155pub trait DifferentialPrivacyStrategy {
156    /// The type of the DP budget, i.e. the variant of differential privacy that can be obtained
157    /// by using this strategy.
158    type Budget: DifferentialPrivacyBudget;
159
160    /// The distribution type this strategy will use to generate the noise.
161    type Distribution: DifferentialPrivacyDistribution;
162
163    /// The type the sensitivity used for privacy analysis has.
164    type Sensitivity;
165
166    /// Create a strategy from a differential privacy budget. The distribution created with
167    /// `create_distribution` should provide the amount of privacy specified here.
168    fn from_budget(b: Self::Budget) -> Self;
169
170    /// Create a new distribution parametrized s.t. adding samples to the result of a function
171    /// with sensitivity `s` will yield differential privacy of the DP variant given in the
172    /// `Budget` type. Can error upon invalid parameters.
173    fn create_distribution(&self, s: Self::Sensitivity) -> Result<Self::Distribution, DpError>;
174}
175
176pub mod distributions;
177mod rand_bigint;
178
179#[cfg(test)]
180mod tests {
181    use serde_json::json;
182
183    use super::PureDpBudget;
184
185    #[test]
186    fn budget_deserialization() {
187        serde_json::from_value::<PureDpBudget>(json!({"epsilon": [[1], [1]]})).unwrap();
188        serde_json::from_value::<PureDpBudget>(json!({"epsilon": [[0], [1]]})).unwrap_err();
189        serde_json::from_value::<PureDpBudget>(json!({"epsilon": [[1], [0]]})).unwrap_err();
190    }
191}
prio/dp.rs

prio/
dp.rs
