论文标题
安全求和：容量区域，集体键和可行性
Secure Summation: Capacity Region, Groupwise Key, and Feasibility
论文作者
论文摘要
考虑了安全的求和问题，其中$ k $用户每个人都有输入，希望在服务器上安全地计算其输入的总和，即，即使服务器最多可与任何最多$ t $用户相关的任何信息，也不会透露超出总和的任何信息。首先，我们证明了安全总和的民间传说结果 - 要确定$ 1 $位的总和，每个用户都需要向服务器发送至少$ 1 $的位，每个用户都需要保持至少$ 1 $的钥匙，并且所有用户都需要集体持有至少$ K -1 $位的某些关键变量。接下来，我们专注于对称的组键设置，其中每组$ g $用户共享一个独立的密钥。我们表明，对于具有$ g> k-t $的对称群体键，安全总和问题是不可行的；当$ g \ leq k-t $，要确定$ 1 $位的总和，每个用户都需要向服务器发送至少$ 1 $ bit，并且每个组键的大小至少为$（k-t-1）/\ binom {k-t} {g} {g} $位。最后，我们放松对组的键和综合用户集上的对称性假设。我们允许任何任意的用户组共享一个独立的密钥和任何任意的用户组与服务器勾结。对于这样的一般组键并勾结用户设置，我们证明，当且仅当且只有当每个节点都是用户而且每个边缘的HyperGraph，并且每个边缘是共享相同键的一组用户时，则安全求和是可行的。
The secure summation problem is considered, where $K$ users, each holds an input, wish to compute the sum of their inputs at a server securely, i.e., without revealing any information beyond the sum even if the server may collude with any set of up to $T$ users. First, we prove a folklore result for secure summation - to compute $1$ bit of the sum securely, each user needs to send at least $1$ bit to the server, each user needs to hold a key of at least $1$ bit, and all users need to hold collectively some key variables of at least $K-1$ bits. Next, we focus on the symmetric groupwise key setting, where every group of $G$ users share an independent key. We show that for symmetric groupwise keys with group size $G$, when $G > K-T$, the secure summation problem is not feasible; when $G \leq K-T$, to compute $1$ bit of the sum securely, each user needs to send at least $1$ bit to the server and the size of each groupwise key is at least $(K-T-1)/\binom{K-T}{G}$ bits. Finally, we relax the symmetry assumption on the groupwise keys and the colluding user sets; we allow any arbitrary group of users to share an independent key and any arbitrary group of users to collude with the server. For such a general groupwise key and colluding user setting, we show that secure summation is feasible if and only if the hypergraph, where each node is a user and each edge is a group of users sharing the same key, is connected after removing the nodes corresponding to any colluding set of users and their incident edges.
