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_HARARY_GRAPH_H_ 18 #define FCP_SECAGG_SERVER_SECRET_SHARING_HARARY_GRAPH_H_ 19 20 #include <vector> 21 22 #include "fcp/secagg/server/secret_sharing_graph.h" 23 24 namespace fcp { 25 namespace secagg { 26 27 // This class represents a regular undirected graph specifying, for each client, 28 // among which other clients it shares its keys and computes pairwise masks. 29 // The construction of the graph is randomized, by permuting node ids, which is 30 // crucial for security. More concretely, the graph is a (degree-1, 31 // num_nodes)-Harary graph with randomly permuted node labels and an additional 32 // self-edge in each node. For simplicity of the construction we require that 33 // the degree is odd. 34 35 // A SecretSharingHararyGraph(num_nodes, degree) graph can be constructed by 36 // putting all num_nodes nodes in a circle and, for each node: (i) adding 37 // degree/2 edges to the immediately preceding nodes, (ii) adding degree/2 edges 38 // to the immediately successive nodes, and (iii) adding a self edge. Finally, 39 // nodes are given ids in [0..num_nodes - 1] uniformaly at random (or 40 // equivalently one applies a permutation to the original ids 0...num_nodes - 41 // 1). 42 43 // For example, if degree = 5 and num_nodes = 10, the adjacency list of a 44 // (num_nodes, degree)-SecretSharingHararyGraph (before permuting ids) is: 45 // 46 // 0 -> 8, 9, 0, 1, 2 47 // 1 -> 9, 0, 1, 2, 3 48 // 2 -> 0, 1, 2, 3, 4 49 // 3 -> 1, 2, 3, 4, 5 50 // 4 -> 2, 3, 4, 5, 6 51 // 5 -> 3, 4, 5, 6, 7 52 // 6 -> 4, 5, 6, 7, 8 53 // 7 -> 5, 6, 7, 8, 9 54 // 8 -> 6, 7, 8, 9, 0 55 // 9 -> 7, 8, 9, 0, 1 56 // 57 // 58 // SecretSharingHararyGraph additionally have permuted node ids (iff is_random 59 // == true) according to a uniformly random permutation. For example, if that 60 // permutation was (3, 2, 5, 4, 1, 8, 9, 0, 6, 7) then the resulting 61 // SecretSharingHararyGraph is the result of applying the permutation (aka node 62 // renaming) to the above adjacency list: 63 64 // 3 -> 6, 7, 3, 2, 5 65 // 2 -> 7, 3, 2, 5, 4 66 // 5 -> 3, 2, 5, 4, 1 67 // 4 -> 2, 5, 4, 1, 8 68 // 1 -> 5, 4, 1, 8, 9 69 // 8 -> 4, 1, 8, 9, 0 70 // 9 -> 1, 8, 9, 0, 6 71 // 0 -> 8, 9, 0, 6, 7 72 // 6 -> 9, 0, 6, 7, 3 73 // 7 -> 0, 6, 7, 3, 1 74 75 // Thus, the outgoing neighbors of 3 are 6, 7, 3, The outgoing neighbors of 2 76 // are 7, 3, 2, and so on. 77 78 // Although the above example aludes to an adjacency list based representation 79 // of the graph, this is only for clarity, as this is not stored explicitly. 80 // Instead, storing the random permutation (that is (3, 2, 5, 4, 1, 8, 9, 0, 6, 81 // 7) in the above example) and its inverse (which is (7, 4, 1, 0, 3, 2, 82 // 8, 9, 5, 6)) leads to a more space efficient implementation with constant 83 // time cost for all class functions. 84 85 // This class must be instantiated through SecretSharingGraphFactory. 86 class SecretSharingHararyGraph : public SecretSharingGraph { 87 public: 88 SecretSharingHararyGraph(const SecretSharingHararyGraph&) = delete; 89 SecretSharingHararyGraph& operator=(const SecretSharingHararyGraph&) = delete; 90 ~SecretSharingHararyGraph() override = default; 91 GetNumNodes()92 int GetNumNodes() const override { return number_of_nodes_; } 93 GetDegree()94 int GetDegree() const override { return degree_; } 95 GetThreshold()96 int GetThreshold() const override { return threshold_; } 97 98 int GetNeighbor(int curr_node, int neighbor_index) const override; 99 100 std::optional<int> GetNeighborIndex(int node_1, int node_2) const override; 101 102 bool AreNeighbors(int node_1, int node_2) const override; 103 104 bool IsOutgoingNeighbor(int node_1, int node_2) const override; 105 106 // Returns the permutation that was applied to the nodes in the construction. 107 // This function is only used for testing purposes. GetPermutationForTesting()108 std::vector<int> GetPermutationForTesting() const { return permutation_; } 109 110 private: 111 int number_of_nodes_; 112 int degree_; 113 int threshold_; 114 // random permutation applied to the node ids in the SecretSharingHararyGraph 115 // construction. 116 const std::vector<int> permutation_; 117 // Inverse of the above permutation. 118 std::vector<int> inverse_permutation_; 119 SecretSharingHararyGraph(int degree, int threshold, 120 std::vector<int> permutation); 121 friend class SecretSharingGraphFactory; 122 IsValidNode(int node)123 bool IsValidNode(int node) const { 124 return 0 <= node && node < number_of_nodes_; 125 } 126 IsValidNeighborIndex(int index)127 bool IsValidNeighborIndex(int index) const { 128 return 0 <= index && index < degree_; 129 } 130 }; 131 132 } // namespace secagg 133 } // namespace fcp 134 135 #endif // FCP_SECAGG_SERVER_SECRET_SHARING_HARARY_GRAPH_H_ 136