1 files changed, 94 insertions, 0 deletions
diff --git a/fcp/secagg/server/secret_sharing_harary_graph.cc b/fcp/secagg/server/secret_sharing_harary_graph.cc
new file mode 100644
index 0000000..d43849a
--- /dev/null
+++ b/fcp/secagg/server/secret_sharing_harary_graph.cc
@@ -0,0 +1,94 @@
+/*
+ * Copyright 2020 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "fcp/secagg/server/secret_sharing_harary_graph.h"
+
+#include <algorithm>
+#include <utility>
+
+#include "absl/strings/str_cat.h"
+#include "fcp/base/monitoring.h"
+#include "fcp/secagg/server/secret_sharing_graph.h"
+
+namespace fcp {
+namespace secagg {
+
+SecretSharingHararyGraph::SecretSharingHararyGraph(int degree, int threshold,
+                                                   std::vector<int> permutation)
+    : number_of_nodes_(static_cast<int>(permutation.size())),
+      degree_(degree),
+      threshold_(threshold),
+      permutation_(std::move(permutation)) {
+  inverse_permutation_ = std::vector<int>(number_of_nodes_);
+  for (int i = 0; i < number_of_nodes_; ++i) {
+    inverse_permutation_[permutation_[i]] = i;
+  }
+}
+
+int SecretSharingHararyGraph::GetNeighbor(int curr_node,
+                                          int neighbor_index) const {
+  FCP_CHECK(IsValidNode(curr_node));
+  FCP_CHECK(IsValidNeighborIndex(neighbor_index));
+
+  int curr_node_before_renaming = inverse_permutation_[curr_node];
+  int zeroth_neighbor_before_renaming = curr_node_before_renaming - degree_ / 2;
+  // We add number_of_nodes_ as a way to handle negative numbers
+  return permutation_[(zeroth_neighbor_before_renaming + neighbor_index +
+                       number_of_nodes_) %
+                      number_of_nodes_];
+}
+
+std::optional<int> SecretSharingHararyGraph::GetNeighborIndex(
+    int node_1, int node_2) const {
+  FCP_CHECK(IsValidNode(node_1));
+  FCP_CHECK(IsValidNode(node_2));
+  int sub_before_renaming =
+      std::abs(inverse_permutation_[node_1] - inverse_permutation_[node_2]);
+  // Compute distance between nodes before applying the permutation.
+  // node_1 and node_2 are connected iff, before renaming, they were at modular
+  // distance <= degree_ / 2
+  int mod_dist_before_renaming =
+      std::min(sub_before_renaming, number_of_nodes_ - sub_before_renaming);
+  if (mod_dist_before_renaming > degree_ / 2) {
+    return {};
+  }
+  // Check that node_2 occurs before node_1 in the list of neighbors of node_1,
+  // i.e. node_2 is an incoming neighbor of node_1
+  // We add number_of_nodes_ as a way to handle negative numbers
+  if ((inverse_permutation_[node_1] - mod_dist_before_renaming +
+       number_of_nodes_) %
+          number_of_nodes_ ==
+      inverse_permutation_[node_2]) {
+    return degree_ / 2 - mod_dist_before_renaming;
+  }
+  return degree_ / 2 + mod_dist_before_renaming;
+}
+
+bool SecretSharingHararyGraph::AreNeighbors(int node_1, int node_2) const {
+  FCP_CHECK(IsValidNode(node_1));
+  FCP_CHECK(IsValidNode(node_2));
+  return GetNeighborIndex(node_1, node_2).value_or(-1) >= 0;
+}
+
+bool SecretSharingHararyGraph::IsOutgoingNeighbor(int node_1,
+                                                  int node_2) const {
+  FCP_CHECK(IsValidNode(node_1));
+  FCP_CHECK(IsValidNode(node_2));
+  return GetNeighborIndex(node_1, node_2).value_or(-1) >= degree_ / 2;
+}
+
+}  // namespace secagg
+}  // namespace fcp