1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

use crate::{
    core::{Domain, Function, Measurement, Metric, MetricSpace},
    domains::{AtomDomain, VectorDomain},
    error::Fallible,
    measures::MaxDivergence,
    metrics::{AbsoluteDistance, L1Distance},
    traits::{samplers::SampleDiscreteLaplaceLinear, CheckAtom},
    traits::{Float, InfCast, Integer},
};

#[cfg(feature = "use-mpfr")]
use opendp_derive::bootstrap;

#[cfg(feature = "use-mpfr")]
use az::SaturatingCast;

#[cfg(feature = "ffi")]
mod ffi;

#[cfg(feature = "use-mpfr")]
mod cks20;
#[cfg(feature = "use-mpfr")]
pub use cks20::*;

mod linear;
pub use linear::*;

#[doc(hidden)]
pub trait MappableDomain: Domain {
    type Atom: Clone;
    fn map_over(
        arg: &Self::Carrier,
        func: &impl Fn(&Self::Atom) -> Fallible<Self::Atom>,
    ) -> Fallible<Self::Carrier>;

    fn new_map_function(
        func: impl Fn(&Self::Atom) -> Fallible<Self::Atom> + 'static,
    ) -> Function<Self::Carrier, Self::Carrier> {
        Function::new_fallible(move |arg: &Self::Carrier| Self::map_over(arg, &func))
    }
}

impl<T: Clone + CheckAtom> MappableDomain for AtomDomain<T> {
    type Atom = T;
    fn map_over(
        arg: &Self::Carrier,
        func: &impl Fn(&Self::Atom) -> Fallible<Self::Atom>,
    ) -> Fallible<Self::Carrier> {
        (func)(arg)
    }
}
impl<D: MappableDomain> MappableDomain for VectorDomain<D> {
    type Atom = D::Atom;
    fn map_over(
        arg: &Vec<D::Carrier>,
        func: &impl Fn(&Self::Atom) -> Fallible<Self::Atom>,
    ) -> Fallible<Self::Carrier> {
        arg.iter().map(|v| D::map_over(v, func)).collect()
    }
}

#[doc(hidden)]
pub trait DiscreteLaplaceDomain: MappableDomain + Default {
    type InputMetric: Metric<Distance = Self::Atom> + Default;
}
impl<T: Clone + CheckAtom> DiscreteLaplaceDomain for AtomDomain<T> {
    type InputMetric = AbsoluteDistance<T>;
}
impl<T: Clone + CheckAtom> DiscreteLaplaceDomain for VectorDomain<AtomDomain<T>> {
    type InputMetric = L1Distance<T>;
}

#[bootstrap(
    features("contrib"),
    arguments(scale(c_type = "void *")),
    generics(D(default = "AtomDomain<int>"))
)]
/// Make a Measurement that adds noise from the discrete_laplace(`scale`) distribution to the input.
///
/// Set `D` to change the input data type and input metric:
///
/// | `D`                          | input type   | `D::InputMetric`       |
/// | ---------------------------- | ------------ | ---------------------- |
/// | `AtomDomain<T>` (default)     | `T`          | `AbsoluteDistance<T>`  |
/// | `VectorDomain<AtomDomain<T>>` | `Vec<T>`     | `L1Distance<T>`        |
///
/// This uses `make_base_discrete_laplace_cks20` if scale is greater than 10, otherwise it uses `make_base_discrete_laplace_linear`.
///
/// # Citations
/// * [GRS12 Universally Utility-Maximizing Privacy Mechanisms](https://theory.stanford.edu/~tim/papers/priv.pdf)
/// * [CKS20 The Discrete Gaussian for Differential Privacy](https://arxiv.org/pdf/2004.00010.pdf#subsection.5.2)
///
/// # Arguments
/// * `scale` - Noise scale parameter for the laplace distribution. `scale` == sqrt(2) * standard_deviation.
///
/// # Generics
/// * `D` - Domain of the data type to be privatized. Valid values are `VectorDomain<AtomDomain<T>>` or `AtomDomain<T>`
/// * `QO` - Data type of the output distance and scale. `f32` or `f64`.
#[cfg(feature = "use-mpfr")]
pub fn make_base_discrete_laplace<D, QO>(
    scale: QO,
) -> Fallible<Measurement<D, D::Carrier, D::InputMetric, MaxDivergence<QO>>>
where
    D: DiscreteLaplaceDomain,
    D::Atom: Integer + SampleDiscreteLaplaceLinear<QO>,
    (D, D::InputMetric): MetricSpace,
    QO: Float + InfCast<D::Atom> + InfCast<D::Atom>,
    rug::Rational: std::convert::TryFrom<QO>,
    rug::Integer: From<D::Atom> + SaturatingCast<D::Atom>,
{
    // benchmarking results at different levels of σ
    // src in /rust/benches/discrete_laplace/main.rs

    // execute bench via:
    //     cargo bench --bench discrete_laplace --features untrusted

    // σ  linear cks20
    // 1   4.907  9.176
    // 2   5.614 10.565
    // 3   6.585 11.592
    // 4   7.450 10.742
    // 5   8.320 12.364
    // 6   9.213 11.722
    // 7  10.106 11.216
    // 8  11.061 10.737
    // 9  11.836 12.884
    // 10 12.653 12.482
    // 11 13.605 12.248
    // 12 14.465 13.320
    // 13 16.545 11.767
    // 14 31.647 15.229
    // 15 25.852 15.177
    // 16 20.179 11.465
    // 17 19.120 13.478
    // 18 19.768 12.982
    // 19 20.777 12.977

    if scale > QO::exact_int_cast(10)? {
        make_base_discrete_laplace_cks20(scale)
    } else {
        make_base_discrete_laplace_linear(scale, None)
    }
}

#[cfg(not(feature = "use-mpfr"))]
pub fn make_base_discrete_laplace<D, QO>(
    scale: QO,
) -> Fallible<Measurement<D, D::Carrier, D::InputMetric, MaxDivergence<QO>>>
where
    D: DiscreteLaplaceDomain,
    (D, D::InputMetric): MetricSpace,
    D::Atom: Integer + SampleDiscreteLaplaceLinear<QO>,
    QO: Float + InfCast<D::Atom>,
{
    make_base_discrete_laplace_linear(scale, None)
}

#[cfg(test)]
mod test {
    use super::*;
    use crate::domains::AtomDomain;

    // there is a distributional test in the accuracy module

    #[test]
    fn test_make_base_discrete_laplace() -> Fallible<()> {
        let meas = make_base_discrete_laplace::<AtomDomain<_>, _>(1f64)?;
        println!("{:?}", meas.invoke(&0)?);
        assert!(meas.check(&1, &1.)?);
        Ok(())
    }
}