Optimal Rate Region for Key Efficient Hierarchical Secure Aggregation with User Collusion

Secure aggregation is concerned with the task of securely uploading the inputs associated with multiple users to an aggregation server without revealing the user inputs to the server besides the summation of all inputs. It finds broad applications in distributed machine learning paradigms such as federated learning (FL). Motivated by practical hierarchical FL systems which utilize the client-edge-cloud network architecture to improve delay performance, we study the hierarchical secure aggregation (HSA) problem in a 3-layer hierarchical network where a total of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$UV$</tex> users are connected to an aggregation server through <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$U$</tex> relay nodes each being associated with a disjoint subset of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$V$</tex> users. Security requires that the server learn nothing beyond the desired sum of the inputs (server security), and each relay learn nothing about the user inputs (relay security) even if they collude with up to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex> users. We characterize the optimal communication and key rate region by proposing a novel secure aggregation scheme and deriving an information-theoretic converse that matches the achievable scheme. In particular, we show that when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T\geq(U-1)V$</tex>, the proposed HSA problem is infeasible. Otherwise when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T &lt; (U-1)V$</tex>, to securely compute 1 bit of the desired sum, each user needs to upload at least 1 bit to its associating relay, each relay needs to upload at least 1 bit to the server, each user needs to hold at least 1 key bit, and all users need to collectively hold at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\max\{V+T, \min\{U+T-1,UV- 1\}\}$</tex> (source) key bits. The characterization of the source key rate is a major contribution of this work.