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 #ifndef FCP_SECAGG_SERVER_SECRET_SHARING_COMPLETE_GRAPH_H_ 18 #define FCP_SECAGG_SERVER_SECRET_SHARING_COMPLETE_GRAPH_H_ 19 20 #include "absl/strings/str_cat.h" 21 #include "fcp/base/monitoring.h" 22 #include "fcp/secagg/server/secret_sharing_graph.h" 23 24 namespace fcp { 25 namespace secagg { 26 27 // SecretSharingGraph built from a complete (directed) graph. 28 // For example, in a SecretSharingCompleteGraph with 4 29 // nodes the list of neighbors of each node are: 30 // 0 -> 0, 1, 2, 3 31 // 1 -> 0, 1, 2, 3 32 // 2 -> 0, 1, 2, 3 33 // 3 -> 0, 1, 2, 3 34 // Thus, the (single) outgoing neighbor of 0 is 0. 35 // The outgoing neighbors of 1 are 0, 1. 36 // The outgoing neighbors of 2 are 0, 1, 2. 37 // The outgoing neighbors of 3 are 0, 1, 2, 3. 38 39 // SecretSharingCompleteGraph must be instantiated via 40 // SecretSharingGraphFactory. 41 class SecretSharingCompleteGraph : public SecretSharingGraph { 42 public: 43 SecretSharingCompleteGraph(const SecretSharingCompleteGraph&) = delete; 44 SecretSharingCompleteGraph& operator=(const SecretSharingCompleteGraph&) = 45 delete; 46 ~SecretSharingCompleteGraph() override = default; 47 GetNumNodes()48 int GetNumNodes() const override { return num_nodes_; } 49 GetDegree()50 int GetDegree() const override { 51 // All nodes have degree num_nodes. 52 return num_nodes_; 53 } 54 GetThreshold()55 int GetThreshold() const override { return threshold_; } 56 GetNeighbor(int curr_node,int i)57 int GetNeighbor(int curr_node, int i) const override { 58 FCP_CHECK(IsValidNode(curr_node)); 59 FCP_CHECK(IsValidNode(i)); // i must be in [0, num_nodes) 60 // Each node has all other nodes as a neighbor, including itself. 61 return i; 62 } 63 GetNeighborIndex(int node_1,int node_2)64 std::optional<int> GetNeighborIndex(int node_1, int node_2) const override { 65 // Lists of neighbors are sorted by client id 66 FCP_CHECK(IsValidNode(node_1)); 67 FCP_CHECK(IsValidNode(node_2)); 68 return node_2; 69 } 70 AreNeighbors(int node_1,int node_2)71 bool AreNeighbors(int node_1, int node_2) const override { 72 FCP_CHECK(IsValidNode(node_1)); 73 FCP_CHECK(IsValidNode(node_2)); 74 return true; 75 } 76 IsOutgoingNeighbor(int node_1,int node_2)77 bool IsOutgoingNeighbor(int node_1, int node_2) const override { 78 FCP_CHECK(IsValidNode(node_1)); 79 FCP_CHECK(IsValidNode(node_2)); 80 return node_2 >= node_1; 81 } 82 83 private: 84 // Number of nodes in the graph, with indices [0, num_nodes). 85 int num_nodes_; 86 int threshold_; SecretSharingCompleteGraph(int num_nodes,int threshold)87 explicit SecretSharingCompleteGraph(int num_nodes, int threshold) 88 : num_nodes_(num_nodes), threshold_(threshold) {} 89 friend class SecretSharingGraphFactory; 90 IsValidNode(int node)91 bool IsValidNode(int node) const { return 0 <= node && node < num_nodes_; } 92 }; 93 94 } // namespace secagg 95 } // namespace fcp 96 97 #endif // FCP_SECAGG_SERVER_SECRET_SHARING_COMPLETE_GRAPH_H_ 98