1 /*
2  * Copyright (C) 2023 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.cobalt.observations;
18 
19 import static com.google.common.base.Preconditions.checkArgument;
20 
21 import com.google.cobalt.PrivateIndexObservation;
22 import com.google.cobalt.ReportDefinition;
23 import com.google.common.collect.ImmutableList;
24 import com.google.common.math.BigDecimalMath;
25 
26 import java.math.BigDecimal;
27 import java.math.RoundingMode;
28 import java.security.SecureRandom;
29 
30 /** Generator for private index observation noise. */
31 public final class PrivacyGenerator {
32     private final SecureRandom mSecureRandom;
33 
PrivacyGenerator(SecureRandom secureRandom)34     public PrivacyGenerator(SecureRandom secureRandom) {
35         this.mSecureRandom = secureRandom;
36     }
37 
38     /**
39      * Generates noise for a report.
40      *
41      * @param maxIndex the maximum private index value for the report
42      * @param reportDefinition the privacy-enabled report containing the privacy parameters
43      * @return private indices that include noise according to the report's privacy parameters
44      */
generateNoise( int maxIndex, ReportDefinition reportDefinition)45     ImmutableList<PrivateIndexObservation> generateNoise(
46             int maxIndex, ReportDefinition reportDefinition) {
47         checkArgument(maxIndex >= 0, "maxIndex value cannot be negative");
48         double lambda = reportDefinition.getShuffledDp().getPoissonMean();
49         checkArgument(lambda > 0, "poisson_mean must be positive, got %s", lambda);
50 
51         // To minimize the number of calls to secureRandom, we draw the total number of
52         // observations, then we distribute those additional observations over the indices. This is
53         // more efficient than drawing from a Poisson distribution once per index when lambda < 1.
54         // We expect lambda << 1 in practice.
55         double lambdaTimesNumIndex =
56                 BigDecimalMath.roundToDouble(
57                         // (maxIndex + 1) * lambda
58                         new BigDecimal(maxIndex)
59                                 .add(BigDecimal.ONE)
60                                 .multiply(BigDecimal.valueOf(lambda)),
61                         // Set rounding mode to rounding upwards in order to prevent accidentally
62                         // using a lower-than-expected noise parameter.
63                         RoundingMode.UP);
64 
65         int addedOnes = samplePoissonDistribution(lambdaTimesNumIndex);
66 
67         ImmutableList.Builder<PrivateIndexObservation> noise = ImmutableList.builder();
68         for (int i = 0; i < addedOnes; ++i) {
69             noise.add(
70                     PrivateIndexObservation.newBuilder()
71                             .setIndex(sampleUniformDistribution(maxIndex))
72                             .build());
73         }
74 
75         return noise.build();
76     }
77 
78     /**
79      * Provides samples from the poisson distribution with mean `lambda`.
80      *
81      * <p>Entropy is provided by a SecureRandom generator. Uses the Inverse transform sampling
82      * method, which is good for small lambda, and requires only one secure random generation. We
83      * expect lambda << 1 in practice. For more details, see
84      * https://en.wikipedia.org/wiki/Poisson_distribution#Random_variate_generation.
85      *
86      * @param lambda the poisson mean
87      * @return the sampled number
88      */
samplePoissonDistribution(double lambda)89     private int samplePoissonDistribution(double lambda) {
90         int x = 0;
91         double p = Math.exp(-lambda);
92         double s = p;
93         double u = mSecureRandom.nextDouble();
94         while (u > s) {
95             x++;
96             p = p * lambda / x;
97             s = s + p;
98         }
99         return x;
100     }
101 
102     /**
103      * Provides samples from the uniform distribution over the integers from 0 to `max`, inclusive.
104      *
105      * <p>Entropy is provided by a SecureRandom generator.
106      *
107      * @param max the maximum number to generate.
108      * @return the sampled number
109      */
sampleUniformDistribution(int max)110     private int sampleUniformDistribution(int max) {
111         return mSecureRandom.nextInt(max + 1);
112     }
113 }
114