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_GRAPH_H_ 18 #define FCP_SECAGG_SERVER_SECRET_SHARING_GRAPH_H_ 19 20 #include "fcp/base/monitoring.h" 21 22 namespace fcp { 23 namespace secagg { 24 25 // Abstract class representing a regular directed graph. 26 // Nodes are integers in [0..NumNodes - 1]. For each node i (representing client 27 // with id i), the graph specifies the set of other nodes with which i shares 28 // its keys and computes pairwise masks. The graph is directed, and the 29 // neighbors of each node are ordered (i.e. we have a notion of the 1st neighbor 30 // of client i, the second neighbor, etc). 31 32 // The intuitive way to visualize the graph is by means of a complete mapping 33 // between nodes and the *ordered* lists of their neighbors (of length the 34 // degree k): 35 36 // 0 - > 1st_neighbor_of_0, ..., kth_neighbor_of_0 37 // 1 - > 1st_neighbor_of_1, ..., kth_neighbor_of_1 38 // ... 39 // n-1 - > 1st_neighbor_of_n-1, ..., kth_neighbor_of_n-1 40 41 // For every node i, its list of neighbors includes i, because as mentioned 42 // above *each node has a self loop*. 43 44 // The direction of each edge adjacent to node i is given implicitly by the 45 // order of the neighbors of i: nodes occurring in the list of neighbors of i 46 // *strictly* after i itself are called *outgoing* neighbors, and nodes ocurring 47 // before i (including i itself) are called *incoming* neighbors. 48 49 // The SecretSharingGraph class includes functions to (a) retrieve the index of 50 // a neighbor of a node in the list of neighbors , (b) retrieve the neighbor of 51 // a node at a given index, and (c) check if a nodes are neighbors, and of which 52 // kind (i.e. incoming vs outgoing). 53 54 // There are multiple subclasses of SecretSharingGraph. The complete graph 55 // variant implemented as the SecretSharingCompleteGraph subclass, and the 56 // (random) Harary graph variant implemented as the SecretSharingCompleteGraph 57 // subclass. 58 class SecretSharingGraph { 59 public: 60 virtual ~SecretSharingGraph() = default; 61 62 // Returns the number of nodes in the graph. 63 virtual int GetNumNodes() const = 0; 64 65 // Returns the degree of the graph. 66 virtual int GetDegree() const = 0; 67 68 // Returns the threshold of the secret sharing 69 virtual int GetThreshold() const = 0; 70 71 // Returns curr_node's ith neighbor. 72 // This function assumes that 0 <= i < GetDegree() and will throw a runtime 73 // error if that's not the case 74 virtual int GetNeighbor(int curr_node, int i) const = 0; 75 76 // Returns the index of node_2 in the list of neighbors of node_1, if present 77 virtual std::optional<int> GetNeighborIndex(int node_1, int node_2) const = 0; 78 79 // Returns true if node_1 and node_2 are neighbors, else false. 80 virtual bool AreNeighbors(int node_1, int node_2) const = 0; 81 82 // Returns true if node_1 is an outgoing neighbor of node_2, else false. 83 virtual bool IsOutgoingNeighbor(int node_1, int node_2) const = 0; 84 }; 85 86 } // namespace secagg 87 } // namespace fcp 88 89 #endif // FCP_SECAGG_SERVER_SECRET_SHARING_GRAPH_H_ 90