1 /*
2  * Copyright 2017 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 android.privacy.internal.longitudinalreporting;
18 
19 import android.privacy.DifferentialPrivacyEncoder;
20 import android.privacy.internal.rappor.RapporConfig;
21 import android.privacy.internal.rappor.RapporEncoder;
22 import android.util.Log;
23 
24 import com.android.internal.annotations.VisibleForTesting;
25 
26 /**
27  * Differential privacy encoder by using Longitudinal Reporting algorithm.
28  *
29  * <b>
30  * Notes: It supports encodeBoolean() only for now.
31  * </b>
32  *
33  * <p>
34  * Definition:
35  * PRR = Permanent Randomized Response
36  * IRR = Instantaneous Randomized response
37  *
38  * Algorithm:
39  * Step 1: Create long-term secrets x(ignoreOriginalInput)=Ber(P), y=Ber(Q), where Ber denotes
40  * Bernoulli distribution on {0, 1}, and we use it as a long-term secret, we implement Ber(x) by
41  * using PRR(2x, 0) when x < 1/2, PRR(2(1-x), 1) when x >= 1/2.
42  * Step 2: If x is 0, report IRR(F, original), otherwise report IRR(F, y)
43  * </p>
44  *
45  * Reference: go/bit-reporting-with-longitudinal-privacy
46  * TODO: Add a public blog / site to explain how it works.
47  *
48  * @hide
49  */
50 public class LongitudinalReportingEncoder implements DifferentialPrivacyEncoder {
51 
52     private static final String TAG = "LongitudinalEncoder";
53     private static final boolean DEBUG = false;
54 
55     // Suffix that will be added to Rappor's encoder id. There's a (relatively) small risk some
56     // other Rappor encoder may re-use the same encoder id.
57     private static final String PRR1_ENCODER_ID = "prr1_encoder_id";
58     private static final String PRR2_ENCODER_ID = "prr2_encoder_id";
59 
60     private final LongitudinalReportingConfig mConfig;
61 
62     // IRR encoder to encode input value.
63     private final RapporEncoder mIRREncoder;
64 
65     // A value that used to replace original value as input, so there's always a chance we are
66     // doing IRR on a fake value not actual original value.
67     // Null if original value does not need to be replaced.
68     private final Boolean mFakeValue;
69 
70     // True if encoder is securely randomized.
71     private final boolean mIsSecure;
72 
73     /**
74      * Create {@link LongitudinalReportingEncoder} with
75      * {@link LongitudinalReportingConfig} provided.
76      *
77      * @param config     Longitudinal Reporting parameters to encode input
78      * @param userSecret User generated secret that used to generate PRR
79      * @return {@link LongitudinalReportingEncoder} instance
80      */
createEncoder(LongitudinalReportingConfig config, byte[] userSecret)81     public static LongitudinalReportingEncoder createEncoder(LongitudinalReportingConfig config,
82             byte[] userSecret) {
83         return new LongitudinalReportingEncoder(config, true, userSecret);
84     }
85 
86     /**
87      * Create <strong>insecure</strong> {@link LongitudinalReportingEncoder} with
88      * {@link LongitudinalReportingConfig} provided.
89      * Should not use it to process sensitive data.
90      *
91      * @param config Rappor parameters to encode input.
92      * @return {@link LongitudinalReportingEncoder} instance.
93      */
94     @VisibleForTesting
createInsecureEncoderForTest( LongitudinalReportingConfig config)95     public static LongitudinalReportingEncoder createInsecureEncoderForTest(
96             LongitudinalReportingConfig config) {
97         return new LongitudinalReportingEncoder(config, false, null);
98     }
99 
LongitudinalReportingEncoder(LongitudinalReportingConfig config, boolean secureEncoder, byte[] userSecret)100     private LongitudinalReportingEncoder(LongitudinalReportingConfig config,
101             boolean secureEncoder, byte[] userSecret) {
102         mConfig = config;
103         mIsSecure = secureEncoder;
104         final boolean ignoreOriginalInput = getLongTermRandomizedResult(config.getProbabilityP(),
105                 secureEncoder, userSecret, config.getEncoderId() + PRR1_ENCODER_ID);
106 
107         if (ignoreOriginalInput) {
108             mFakeValue = getLongTermRandomizedResult(config.getProbabilityQ(),
109                     secureEncoder, userSecret, config.getEncoderId() + PRR2_ENCODER_ID);
110         } else {
111             // Not using fake value, so IRR will be processed on real input value.
112             mFakeValue = null;
113         }
114 
115         final RapporConfig irrConfig = config.getIRRConfig();
116         mIRREncoder = secureEncoder
117                 ? RapporEncoder.createEncoder(irrConfig, userSecret)
118                 : RapporEncoder.createInsecureEncoderForTest(irrConfig);
119     }
120 
121     @Override
encodeString(String original)122     public byte[] encodeString(String original) {
123         throw new UnsupportedOperationException();
124     }
125 
126     @Override
encodeBoolean(boolean original)127     public byte[] encodeBoolean(boolean original) {
128         if (DEBUG) {
129             Log.d(TAG, "encodeBoolean, encoderId:" + mConfig.getEncoderId() + ", original: "
130                     + original);
131         }
132         if (mFakeValue != null) {
133             // Use the fake value generated in PRR.
134             original = mFakeValue.booleanValue();
135             if (DEBUG) Log.d(TAG, "Use fake value: " + original);
136         }
137         byte[] result = mIRREncoder.encodeBoolean(original);
138         if (DEBUG) Log.d(TAG, "result: " + ((result[0] & 0x1) != 0));
139         return result;
140     }
141 
142     @Override
encodeBits(byte[] bits)143     public byte[] encodeBits(byte[] bits) {
144         throw new UnsupportedOperationException();
145     }
146 
147     @Override
getConfig()148     public LongitudinalReportingConfig getConfig() {
149         return mConfig;
150     }
151 
152     @Override
isInsecureEncoderForTest()153     public boolean isInsecureEncoderForTest() {
154         return !mIsSecure;
155     }
156 
157     /**
158      * Get PRR result that with probability p is 1, probability 1-p is 0.
159      */
160     @VisibleForTesting
getLongTermRandomizedResult(double p, boolean secureEncoder, byte[] userSecret, String encoderId)161     public static boolean getLongTermRandomizedResult(double p, boolean secureEncoder,
162             byte[] userSecret, String encoderId) {
163         // Use Rappor to get PRR result. Rappor's P and Q are set to 0 and 1 so IRR will not be
164         // effective.
165         // As Rappor has rapporF/2 chance returns 0, rapporF/2 chance returns 1, and 1-rapporF
166         // chance returns original input.
167         // If p < 0.5, setting rapporF=2p and input=0 will make Rappor has p chance to return 1
168         // P(output=1 | input=0) = rapporF/2 = 2p/2 = p.
169         // If p >= 0.5, setting rapporF=2(1-p) and input=1 will make Rappor has p chance
170         // to return 1.
171         // P(output=1 | input=1) = rapporF/2 + (1 - rapporF) = 2(1-p)/2 + (1 - 2(1-p)) = p.
172         final double effectiveF = p < 0.5f ? p * 2 : (1 - p) * 2;
173         final boolean prrInput = p < 0.5f ? false : true;
174         final RapporConfig prrConfig = new RapporConfig(encoderId, 1, effectiveF,
175                 0, 1, 1, 1);
176         final RapporEncoder encoder = secureEncoder
177                 ? RapporEncoder.createEncoder(prrConfig, userSecret)
178                 : RapporEncoder.createInsecureEncoderForTest(prrConfig);
179         return encoder.encodeBoolean(prrInput)[0] > 0;
180     }
181 }
182