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/secret_sharing_harary_graph.h"
18
19 #include <algorithm>
20 #include <utility>
21
22 #include "absl/strings/str_cat.h"
23 #include "fcp/base/monitoring.h"
24 #include "fcp/secagg/server/secret_sharing_graph.h"
25
26 namespace fcp {
27 namespace secagg {
28
SecretSharingHararyGraph(int degree,int threshold,std::vector<int> permutation)29 SecretSharingHararyGraph::SecretSharingHararyGraph(int degree, int threshold,
30 std::vector<int> permutation)
31 : number_of_nodes_(static_cast<int>(permutation.size())),
32 degree_(degree),
33 threshold_(threshold),
34 permutation_(std::move(permutation)) {
35 inverse_permutation_ = std::vector<int>(number_of_nodes_);
36 for (int i = 0; i < number_of_nodes_; ++i) {
37 inverse_permutation_[permutation_[i]] = i;
38 }
39 }
40
GetNeighbor(int curr_node,int neighbor_index) const41 int SecretSharingHararyGraph::GetNeighbor(int curr_node,
42 int neighbor_index) const {
43 FCP_CHECK(IsValidNode(curr_node));
44 FCP_CHECK(IsValidNeighborIndex(neighbor_index));
45
46 int curr_node_before_renaming = inverse_permutation_[curr_node];
47 int zeroth_neighbor_before_renaming = curr_node_before_renaming - degree_ / 2;
48 // We add number_of_nodes_ as a way to handle negative numbers
49 return permutation_[(zeroth_neighbor_before_renaming + neighbor_index +
50 number_of_nodes_) %
51 number_of_nodes_];
52 }
53
GetNeighborIndex(int node_1,int node_2) const54 std::optional<int> SecretSharingHararyGraph::GetNeighborIndex(
55 int node_1, int node_2) const {
56 FCP_CHECK(IsValidNode(node_1));
57 FCP_CHECK(IsValidNode(node_2));
58 int sub_before_renaming =
59 std::abs(inverse_permutation_[node_1] - inverse_permutation_[node_2]);
60 // Compute distance between nodes before applying the permutation.
61 // node_1 and node_2 are connected iff, before renaming, they were at modular
62 // distance <= degree_ / 2
63 int mod_dist_before_renaming =
64 std::min(sub_before_renaming, number_of_nodes_ - sub_before_renaming);
65 if (mod_dist_before_renaming > degree_ / 2) {
66 return {};
67 }
68 // Check that node_2 occurs before node_1 in the list of neighbors of node_1,
69 // i.e. node_2 is an incoming neighbor of node_1
70 // We add number_of_nodes_ as a way to handle negative numbers
71 if ((inverse_permutation_[node_1] - mod_dist_before_renaming +
72 number_of_nodes_) %
73 number_of_nodes_ ==
74 inverse_permutation_[node_2]) {
75 return degree_ / 2 - mod_dist_before_renaming;
76 }
77 return degree_ / 2 + mod_dist_before_renaming;
78 }
79
AreNeighbors(int node_1,int node_2) const80 bool SecretSharingHararyGraph::AreNeighbors(int node_1, int node_2) const {
81 FCP_CHECK(IsValidNode(node_1));
82 FCP_CHECK(IsValidNode(node_2));
83 return GetNeighborIndex(node_1, node_2).value_or(-1) >= 0;
84 }
85
IsOutgoingNeighbor(int node_1,int node_2) const86 bool SecretSharingHararyGraph::IsOutgoingNeighbor(int node_1,
87 int node_2) const {
88 FCP_CHECK(IsValidNode(node_1));
89 FCP_CHECK(IsValidNode(node_2));
90 return GetNeighborIndex(node_1, node_2).value_or(-1) >= degree_ / 2;
91 }
92
93 } // namespace secagg
94 } // namespace fcp
95