1 /*
2 * Copyright 2020 Google LLC
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 #include "fcp/secagg/server/graph_parameter_finder.h"
18
19 #include <algorithm>
20 #include <cmath>
21 #include <memory>
22 #include <optional>
23
24 #include "fcp/base/monitoring.h"
25 #include "fcp/secagg/server/distribution_utilities.h"
26 #include "fcp/secagg/server/secagg_server_enums.pb.h"
27
28 namespace fcp {
29 namespace secagg {
30
31 class HararyGraphParameterFinder {
32 public:
33 // Checks that parameters have valid values and returns an instance of the
34 // class
Create(int number_of_clients,double adversarial_rate,double dropout_rate,AdversaryClass adversary_class)35 static StatusOr<std::unique_ptr<HararyGraphParameterFinder>> Create(
36 int number_of_clients, double adversarial_rate, double dropout_rate,
37 AdversaryClass adversary_class) {
38 if (number_of_clients <= 0) {
39 return FCP_STATUS(FAILED_PRECONDITION)
40 << "The number of clients should greater than zero. Value "
41 "provided = "
42 << number_of_clients;
43 }
44 if (number_of_clients > kMaxNumberOfClients) {
45 return FCP_STATUS(FAILED_PRECONDITION)
46 << "The valid number of clients is upper bounded by 1M. There is "
47 "no "
48 "fundamental reason for that, and this "
49 "parameter finder should work for that setting. Just add the "
50 "corresponding tests.";
51 }
52 if (adversarial_rate < 0 || adversarial_rate >= 1) {
53 return FCP_STATUS(FAILED_PRECONDITION)
54 << "The adversarial rate should be in [0,1). Value provided = "
55 << adversarial_rate;
56 }
57 if (dropout_rate < 0 || dropout_rate >= 1) {
58 return FCP_STATUS(FAILED_PRECONDITION)
59 << "The dropout rate should be in [0,1). Value provided = "
60 << dropout_rate;
61 }
62 FCP_CHECK(adversary_class == AdversaryClass::CURIOUS_SERVER ||
63 adversary_class == AdversaryClass::SEMI_MALICIOUS_SERVER ||
64 adversary_class == AdversaryClass::NONE)
65 << "CURIOUS_SERVER, SEMI_MALICIOUS_SERVER, and NONE are the only "
66 "supported "
67 "adversary classes.";
68 if (adversary_class == AdversaryClass::NONE && adversarial_rate > 0) {
69 return FCP_STATUS(FAILED_PRECONDITION)
70 << "The no-adversary setting expects that adversarial_rate = 0. "
71 "Value provided = "
72 << adversarial_rate;
73 }
74 if ((adversary_class == AdversaryClass::CURIOUS_SERVER ||
75 adversary_class == AdversaryClass::NONE) &&
76 adversarial_rate + dropout_rate > .9) {
77 return FCP_STATUS(FAILED_PRECONDITION)
78 << "In the semi-honest and no-adversary settings, "
79 "adversarial_rate + dropout_rate "
80 "<= 0.9 must hold for the instance to be feasible. Values "
81 "provided = "
82 << adversarial_rate << " and " << dropout_rate;
83 }
84 if (adversary_class == AdversaryClass::SEMI_MALICIOUS_SERVER &&
85 adversarial_rate + 2 * dropout_rate > .9) {
86 return FCP_STATUS(FAILED_PRECONDITION)
87 << "In the semi-malicious setting, adversarial_rate + "
88 "2*dropout_rate <= 0.9 must hold for the instance to be "
89 "feasible. Values provided = "
90 << adversarial_rate << " and " << dropout_rate;
91 }
92 return absl::WrapUnique(new HararyGraphParameterFinder(
93 number_of_clients, adversarial_rate, dropout_rate, adversary_class));
94 }
95
96 // Returns the degree of a Harary graph and threshold of a Shamir secret
97 // sharing scheme that result in an instance of subgraph-secagg with
98 // statistical security [kSecurityParameter] and failure probability less
99 // that 2**(-[kCorrectnessParameter]), assuming [number_of_clients_]
100 // participants and a fraction of [adversarial_rate_] (resp. [dropout_rate_])
101 // adversarial clients (resp. dropouts).
ComputeDegreeAndThreshold()102 StatusOr<HararyGraphParameters> ComputeDegreeAndThreshold() {
103 for (int number_of_neighbors = 2;
104 number_of_neighbors < number_of_clients_ - 1;
105 number_of_neighbors += 2) {
106 auto threshold = CheckNumberOfNeighbors(number_of_neighbors);
107 if (threshold.has_value()) {
108 HararyGraphParameters params = {number_of_clients_, number_of_neighbors,
109 threshold.value()};
110 return params;
111 }
112 }
113 return FCP_STATUS(FAILED_PRECONDITION)
114 << "Parameters consistent with the provided aggregation "
115 "requirements were not found. Unless the number of clients is "
116 "small (<500) and adversarial rate plus dropout rate are large "
117 "(close to 1), this is an unlikely error that should be "
118 "investigated as a bug.";
119 }
120
121 private:
122 static constexpr int kMaxNumberOfClients = 1000000;
123
124 // Statistical security parameter. Parameters found by
125 // HararyGraphParameterFinder guarantee statistical security with probability
126 // > 1-2^{-40}
127 static constexpr double kSecurityParameter = 40;
128 // Statistical correctness parameter. Parameters found by
129 // HararyGraphParameterFinder guarantee a failure probability < 2^{-20}
130 static constexpr double kCorrectnessParameter = 20;
131
132 // Adding kSmall stops the floating point rounding error being magnified in
133 // an insecure direction by the rounding. Being small it is unlikely to
134 // introduce an error the other way either but that would only slightly hit
135 // performance anyway.
136 static constexpr double kSmall = 1e-14;
137
138 int number_of_clients_;
139 double adversarial_rate_;
140 double dropout_rate_;
141 AdversaryClass adversary_class_;
142
143 // Returns a bound on the probability p of a random harary graph of
144 // number_of_clients_ nodes and degree number_of_neighbors being disconnected
145 // after adversarial and dropout nodes are removed.
LogProbOfDisconnectedRandomHarary(int number_of_neighbors)146 double LogProbOfDisconnectedRandomHarary(int number_of_neighbors) {
147 // Note that any set of removed nodes disconnecting a Harary graph needs to
148 // include number_of_neighbors/2 successive clients in two disjoint places
149 // (in the ring forming the Harary graph). In our setting that means that
150 // these clients need to be adversarial or dropouts. There are
151 // number_of_clients_ ways to pick the first break and
152 // number_of_clients_-number_of_neighbors-1 ways to pick the other, and this
153 // double counts the pairs so dividing by two gives the number of gap pairs.
154 // For each pair this probability is given by the ratio of the given
155 // factorials. Multiplying by number_of_gap_pairs bounds the total
156 // probability by a union bound.
157 double log_number_of_gap_pairs =
158 std::log(number_of_clients_) +
159 std::log(number_of_clients_ - number_of_neighbors - 1) - std::log(2);
160 int max_adversarial_clients = static_cast<int>(
161 std::floor((adversarial_rate_ + kSmall) * number_of_clients_));
162 int max_dropout_clients = static_cast<int>(
163 std::floor((dropout_rate_ + kSmall) * number_of_clients_));
164 int max_bad_clients = max_adversarial_clients + max_dropout_clients;
165
166 if (number_of_neighbors > max_bad_clients) return -HUGE_VAL;
167 double ret = log_number_of_gap_pairs + std::lgamma(max_bad_clients + 1) +
168 std::lgamma(number_of_clients_ - number_of_neighbors + 1) -
169 std::lgamma(number_of_clients_ + 1) -
170 std::lgamma(max_bad_clients - number_of_neighbors + 1);
171 return ret;
172 }
173
174 // Checks if degree number_of_neighbors_ results in a secure and correct
175 // protocol, and returns an appropriate threshold if so.
CheckNumberOfNeighbors(int number_of_neighbors)176 std::optional<int> CheckNumberOfNeighbors(int number_of_neighbors) {
177 // We split the security parameter evenly across the two bad events
178 constexpr double kSecurityParameterPerEvent = kSecurityParameter + 1;
179 const double kLogProbSecurityParameterPerEvent =
180 -kSecurityParameterPerEvent * std::log(2);
181 // We first check that the graph of honest surviving nodes is connected with
182 // large enough probability
183 if (LogProbOfDisconnectedRandomHarary(number_of_neighbors) >=
184 kLogProbSecurityParameterPerEvent) {
185 // The probability of the graph getting disconnected is not small enough
186 return std::nullopt;
187 }
188
189 // We now check find threshold t such that (a) for every client i, the
190 // number of adversarial neighbors of i is greater than t-1 with small
191 // enough probability, and (b) that the number of surviving nodes of a
192 // client is greater than t-1 with large enough probability.
193 int upper_bound_adversarial_clients = static_cast<int>(
194 std::floor((adversarial_rate_ + kSmall) * number_of_clients_));
195 int lower_bound_surviving_clients = static_cast<int>(
196 std::ceil((1 - dropout_rate_ - kSmall) * number_of_clients_));
197 // Distribution of the number of adversarial neighbors of a client
198 auto num_adversarial_neighbors = HypergeometricDistribution::Create(
199 number_of_clients_, upper_bound_adversarial_clients,
200 number_of_neighbors);
201 // Distribution of the number of dropout neighbors of a client
202 auto num_surviving_neighbors = HypergeometricDistribution::Create(
203 number_of_clients_, lower_bound_surviving_clients, number_of_neighbors);
204
205 // t1 is such that Pr[# of adversarial neighbors of a client > t1] <=
206 // 2^{-security_parameter_per_event} / number_of_clients_
207
208 // t2 is such that Pr[# of adversarial neighbors of a client <= t2] >=
209 // 2^{-correctness_parameter_} / number_of_clients_
210
211 // The result of the below quantile functions is an integer result rounded
212 // outwards i.e. away from the median of the distribution.
213 auto t1 = num_adversarial_neighbors.value()->FindQuantile(
214 std::pow(2, -kSecurityParameterPerEvent) / number_of_clients_, true);
215 auto t2 = num_surviving_neighbors.value()->FindQuantile(
216 std::pow(2, -kCorrectnessParameter) / number_of_clients_);
217 if (num_surviving_neighbors.value()->CDF(t2) <
218 std::pow(2, -kCorrectnessParameter) / number_of_clients_) {
219 t2++;
220 }
221
222 // In the semihonest case, the returned threshold must satisfy that t \in
223 // (t1, t2]. To save computation when reconstructing shamir shares we simply
224 // choose t1+1.
225
226 // In the semi-malicious case t should be such that Pr[2t -
227 // number_of_neighbors] < 2^{-security_parameter_ + 1} / number_of_clients_,
228 // and thus we set t1 + 1 to be at least t1/2 + number_of_neighbors/2 + 1/2,
229 // so that also in this case (t1, t2] defines the range of acceptable values
230 // for t
231
232 if (adversary_class_ == AdversaryClass::SEMI_MALICIOUS_SERVER) {
233 t1 = std::ceil((t1 + number_of_neighbors - 1.25) / 2);
234 }
235 if (t2 <= t1) {
236 return std::nullopt;
237 }
238 // The Shamir secret sharing implementation requires that threshold is >= 2
239 return std::max(t1 + 1, 2.);
240 }
241
HararyGraphParameterFinder(int number_of_clients,double adversarial_rate,double dropout_rate,AdversaryClass adversary_class)242 HararyGraphParameterFinder(int number_of_clients, double adversarial_rate,
243 double dropout_rate,
244 AdversaryClass adversary_class)
245 : number_of_clients_(number_of_clients),
246 adversarial_rate_(adversarial_rate),
247 dropout_rate_(dropout_rate),
248 adversary_class_(adversary_class) {}
249 };
250
ComputeHararyGraphParameters(int number_of_clients,SecureAggregationRequirements threat_model)251 StatusOr<HararyGraphParameters> ComputeHararyGraphParameters(
252 int number_of_clients, SecureAggregationRequirements threat_model) {
253 FCP_ASSIGN_OR_RETURN(
254 auto pf, HararyGraphParameterFinder::Create(
255 number_of_clients, threat_model.adversarial_client_rate(),
256 threat_model.estimated_dropout_rate(),
257 threat_model.adversary_class()));
258 return pf->ComputeDegreeAndThreshold();
259 }
260
CheckFullGraphParameters(int number_of_clients,int threshold,SecureAggregationRequirements threat_model)261 Status CheckFullGraphParameters(int number_of_clients, int threshold,
262 SecureAggregationRequirements threat_model) {
263 if (number_of_clients <= 0) {
264 return FCP_STATUS(FAILED_PRECONDITION)
265 << "The number of clients should greater than zero. Value "
266 "provided = "
267 << number_of_clients;
268 }
269 if (threshold <= 1 || threshold > number_of_clients) {
270 return FCP_STATUS(FAILED_PRECONDITION)
271 << "The threshold should be > 1 and <= number_of_clients. Value "
272 "provided = "
273 << threshold;
274 }
275 if (threat_model.adversarial_client_rate() < 0 ||
276 threat_model.adversarial_client_rate() >= 1) {
277 return FCP_STATUS(FAILED_PRECONDITION)
278 << "The adversarial rate should be in [0,1). Value provided = "
279 << threat_model.adversarial_client_rate();
280 }
281 if (threat_model.estimated_dropout_rate() < 0 ||
282 threat_model.estimated_dropout_rate() >= 1) {
283 return FCP_STATUS(FAILED_PRECONDITION)
284 << "The dropout rate should be in [0,1). Value provided = "
285 << threat_model.estimated_dropout_rate();
286 }
287 FCP_CHECK(threat_model.adversary_class() == AdversaryClass::CURIOUS_SERVER ||
288 threat_model.adversary_class() ==
289 AdversaryClass::SEMI_MALICIOUS_SERVER ||
290 threat_model.adversary_class() == AdversaryClass::NONE)
291 << "CURIOUS_SERVER, SEMI_MALICIOUS_SERVER, and NONE are the only "
292 "supported "
293 "adversary classes.";
294 if (threshold < std::ceil((1 - threat_model.estimated_dropout_rate()) *
295 number_of_clients)) {
296 return FCP_STATUS(FAILED_PRECONDITION)
297 << "The threshold should be at least ceil(1 - dropout_rate * "
298 "number_of_clients). Values provided are "
299 << threshold << ", "
300 << std::floor((1 - threat_model.estimated_dropout_rate()) *
301 number_of_clients);
302 }
303 if (threat_model.adversary_class() == AdversaryClass::CURIOUS_SERVER &&
304 threshold <= std::ceil(threat_model.adversarial_client_rate() *
305 number_of_clients)) {
306 return FCP_STATUS(FAILED_PRECONDITION)
307 << "In the full-graph variant and CURIOUS_SERVER threat model, the "
308 "threshold should be at least ceil(adversarial_client_rate * "
309 "number_of_clients). Values provided are "
310 << threshold << ", "
311 << std::ceil(threat_model.adversarial_client_rate() *
312 number_of_clients);
313 } else if (threat_model.adversary_class() ==
314 AdversaryClass::SEMI_MALICIOUS_SERVER &&
315 threshold <= std::ceil((number_of_clients +
316 threat_model.adversarial_client_rate() *
317 number_of_clients) /
318 2)) {
319 return FCP_STATUS(FAILED_PRECONDITION)
320 << "In the full-graph variant and SEMI_MALICIOUS_SERVER threat "
321 "model, the threshold should be at least "
322 "ceil((total_number_of_clients "
323 "+ adversarial_client_rate * number_of_clients) / 2). "
324 "Values provided are "
325 << threshold << ", "
326 << (number_of_clients +
327 std::ceil(threat_model.adversarial_client_rate() *
328 number_of_clients) /
329 2);
330 }
331 return FCP_STATUS(OK);
332 }
333
334 } // namespace secagg
335 } // namespace fcp
336