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 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282
use smartnoise_validator::errors::*; use crate::utilities; use smartnoise_validator::Float; use crate::utilities::{noise}; use smartnoise_validator::components::gaussian_mechanism::get_analytic_gaussian_sigma; use std::ops::{Div}; /// Returns noise drawn according to the Laplace mechanism /// /// Noise is drawn with scale sensitivity/epsilon and centered about 0. /// For more information, see the Laplace mechanism in /// C. Dwork, A. Roth The Algorithmic Foundations of Differential Privacy, Chapter 3.3 The Laplace Mechanism p.30-37. August 2014. /// /// NOTE: this implementation of Laplace draws is likely non-private due to floating-point attacks /// See [Mironov (2012)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.366.5957&rep=rep1&type=pdf) /// for more information /// /// # Arguments /// * `value` - Statistic to be privatized. /// * `epsilon` - Multiplicative privacy loss parameter. /// * `sensitivity` - Upper bound on the L1 sensitivity of the function you want to privatize. /// * `enforce_constant_time` - Whether or not to enforce the algorithm to run in constant time /// /// # Return /// A single value drawn from the Laplace distribution with scale sensitivity/epsilon centered about 0. /// /// # Examples /// ``` /// use smartnoise_runtime::utilities::mechanisms::laplace_mechanism; /// let n = laplace_mechanism(22.3, 0.1, 2.0, false); /// ``` pub fn laplace_mechanism( value: f64, epsilon: f64, sensitivity: f64, enforce_constant_time: bool ) -> Result<f64> { if sensitivity < 0. { return Err(format!("sensitivity ({}) must be non-negative", sensitivity).into()); } if epsilon <= 0. { return Err(format!("epsilon ({}) must be positive", epsilon).into()) } let scale: f64 = sensitivity / epsilon; noise::sample_laplace(0., scale, enforce_constant_time).map(|n| value + n) } /// Computes privatized value according to the Snapping mechanism /// /// Developed as a variant of the Laplace mechanism which does not suffer from floating-point side channel attacks. /// For more information, see [Mironov (2012)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.366.5957&rep=rep1&type=pdf) /// /// # Arguments /// * `value` - Non-private value of the statistic to be privatized. /// * `epsilon` - Desired privacy guarantee. /// * `sensitivity` - l1 Sensitivity of function to which mechanism is being applied. /// * `min` - Lower bound on function value being privatized. /// * `max` - Upper bound on function value being privatized. /// * `binding_probability` - Optional. Probability of binding on the final clamp /// * `enforce_constant_time` - Whether or not to enforce the algorithm to run in constant time /// /// # Returns /// Result of snapping mechanism /// /// # Example /// ``` /// use smartnoise_runtime::utilities::mechanisms::snapping_mechanism; /// let value: f64 = 50.0; /// let epsilon: f64 = 1.0; /// let min: f64 = -50.; /// let max: f64 = 150.0; /// let sensitivity: f64 = 1.0/1000.0; /// let precision: i64 = 118; /// snapping_mechanism(value, epsilon, sensitivity, min, max, None, false).unwrap(); /// println!("snapped value: {}", value); /// ``` pub fn snapping_mechanism( mut value: f64, epsilon: f64, sensitivity: f64, min: f64, max: f64, binding_probability: Option<f64>, enforce_constant_time: bool ) -> Result<f64> { if sensitivity < 0. { return Err(format!("sensitivity ({}) must be non-negative", sensitivity).into()); } if epsilon <= 0. { return Err(format!("epsilon ({}) must be positive", epsilon).into()) } if min > max { return Err("lower may not be greater than upper".into()) } let mut b = (max - min) / 2.; let shift = min + b; // ~~ preprocess ~~ // (A) shift mechanism input to be about zero value -= shift; // (B) clamp by b value = num::clamp(value, -b.abs(), b.abs()); // (C) scale by sensitivity, to convert quantity to sensitivity-1 value /= sensitivity; b /= sensitivity; // ~~ internals ~~ let (mut value, epsilon) = noise::apply_snapping_noise(value, epsilon, b, enforce_constant_time)?; if let Some(binding_probability) = binding_probability { b += (1.0 - 2.0 * (1.0 - binding_probability).ln()) / epsilon; } // ~~ postprocess ~~ // (C) return to original scale value *= sensitivity; b *= sensitivity; // (B) re-clamp by b value = num::clamp(value, -b.abs(), b.abs()); // (A) shift mechanism output back to original location value += shift; Ok(value) } /// Returns noise drawn according to the Gaussian mechanism. /// /// If using the standard guassian, /// Let c = sqrt(2*ln(1.25/delta)). Noise is drawn from a Gaussian distribution with scale /// sensitivity*c/epsilon and centered about 0. /// For more information, see the Gaussian mechanism in /// C. Dwork, A. Roth The Algorithmic Foundations of Differential Privacy, Chapter 3.5.3 Laplace versus Gauss p.53. August 2014. /// /// If using the analytic gaussian, /// the noise scale is derived using [Balle (2018)](https://arxiv.org/pdf/1805.06530.pdf). /// /// NOTE: this implementation of Gaussian draws in likely non-private due to floating-point attacks /// See [Mironov (2012)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.366.5957&rep=rep1&type=pdf) /// for more information on a similar attack of the Laplace mechanism. /// /// # Arguments /// * `value` - Statistic to be privatized. /// * `epsilon` - Multiplicative privacy loss parameter. /// * `delta` - Additive privacy loss parameter. /// * `sensitivity` - Upper bound on the L2 sensitivity of the function you want to privatize. /// * `enforce_constant_time` - Whether or not to enforce the algorithm to run in constant time /// /// # Return /// A draw from Gaussian distribution with scale defined as above. /// /// # Examples /// ``` /// use smartnoise_runtime::utilities::mechanisms::gaussian_mechanism; /// let n = gaussian_mechanism(22.3, 0.1, 0.0001, 2.0, false, false); /// ``` pub fn gaussian_mechanism( value: f64, epsilon: f64, delta: f64, sensitivity: f64, analytic: bool, enforce_constant_time: bool ) -> Result<f64> { if epsilon <= 0. || delta <= 0. || sensitivity <= 0. { return Err(format!("epsilon ({}), delta ({}) and sensitivity ({}) must all be positive", epsilon, delta, sensitivity).into()); } let scale = if analytic { get_analytic_gaussian_sigma(epsilon, delta, sensitivity) } else { sensitivity * (2. * (1.25 / delta).ln()).sqrt() / epsilon }; // this uses mpfr noise if available Ok(value + noise::sample_gaussian(0., scale, enforce_constant_time)?) } /// Returns noise drawn according to the Geometric mechanism. /// /// Uses the Geometric mechanism as originally proposed in /// [Ghosh, Roughgarden, & Sundarajan (2012)](https://theory.stanford.edu/~tim/papers/priv.pdf). /// We are calling this the `simple_geometric_mechanism` because there is some hope that we will later /// add other versions, such as those developed in [Balcer & Vadhan (2019)](https://arxiv.org/pdf/1709.05396.pdf) /// /// # Arguments /// * `value` - Statistic to be privatized. /// * `epsilon` - Multiplicative privacy loss parameter /// * `sensitivity` - L1 sensitivity of function you want to privatize. The Geometric is typically used for counting queries, where sensitivity = 1. /// * `min` - The minimum return you think possible. /// * `max` - The maximum return you think possible. /// * `enforce_constant_time` - Whether or not to run the noise generation algorithm in constant time. /// If true, will run max-min number of times. /// # Return /// A draw according to the Geometric mechanism. /// /// # Examples /// ``` /// use smartnoise_runtime::utilities::mechanisms::simple_geometric_mechanism; /// let n = simple_geometric_mechanism(4, 0.1, 1., 0, 10, true); /// ``` pub fn simple_geometric_mechanism( value: i64, epsilon: f64, sensitivity: f64, min: i64, max: i64, enforce_constant_time: bool ) -> Result<i64> { if epsilon < 0. || sensitivity < 0. { return Err(format!("epsilon ({}) and sensitivity ({}) must be positive", epsilon, sensitivity).into()); } let scale: f64 = sensitivity / epsilon; let noised = value + noise::sample_simple_geometric_mechanism(scale, min, max, enforce_constant_time)?; Ok(if noised < min {min} else if noised > max { max } else { noised }) } /// Returns data element according to the Exponential mechanism. /// /// # Arguments /// /// * `epsilon` - Multiplicative privacy loss parameter. /// * `sensitivity` - L1 sensitivity of utility function. /// * `candidate_set` - Data from which user wants an element returned. /// * `utility` - Utility function used within the exponential mechanism. /// * `enforce_constant_time` - Whether or not to enforce the algorithm to run in constant time /// /// NOTE: This implementation is likely non-private because of the difference between theory on /// the real numbers and floating-point numbers. See [Ilvento 2019](https://arxiv.org/abs/1912.04222) for /// more information on the problem and a proposed fix. /// /// # Example /// ``` /// use ndarray::prelude::*; /// use smartnoise_runtime::utilities::mechanisms::exponential_mechanism; /// // create utility function /// pub fn utility(x:&f64) -> f64 { /// let util = *x as f64; /// return util; /// } /// /// /// // create sample data /// let xs: Vec<f64> = vec![1., 2., 3., 4., 5.]; /// let utilities: Vec<f64> = xs.iter().map(utility).collect(); /// let ans = exponential_mechanism(1.0, 1.0, &xs, utilities, false); /// # ans.unwrap(); /// ``` #[cfg(feature = "use-mpfr")] pub fn exponential_mechanism<T>( epsilon: f64, sensitivity: f64, candidate_set: &[T], utilities: Vec<f64>, enforce_constant_time: bool ) -> Result<T> where T: Clone, { macro_rules! to_rug {($v:expr) => {rug::Float::with_val(53, $v)}} // get vector of e^(scaled util), then use to find probabilities let scaling = to_rug!(epsilon).div(to_rug!(2. * sensitivity)); // establish selection probabilities for each element let e_util_vec: Vec<rug::Float> = utilities.into_iter() .map(|util| (to_rug!(util) * &scaling).exp()) .collect(); let sum_e_util_vec = to_rug!(rug::Float::sum(e_util_vec.iter())); let probability_vec: Vec<Float> = e_util_vec.into_iter() .map(|x| (x / sum_e_util_vec.clone()).to_f64() as Float) .collect(); // sample element relative to probability utilities::sample_from_set(candidate_set, &probability_vec, enforce_constant_time) } #[cfg(not(feature = "use-mpfr"))] pub fn exponential_mechanism<T>( epsilon: f64, sensitivity: f64, candidate_set: &[T], utilities: Vec<f64>, enforce_constant_time: bool ) -> Result<T> where T: Clone, { // get vector of e^(util), and sample_from_set accepts weights let weight_vec: Vec<f64> = utilities.into_iter() .map(|x| (epsilon * x / (2. * sensitivity)).exp()).collect(); // sample element relative to probability utilities::sample_from_set(candidate_set, &weight_vec, enforce_constant_time) }