On the Randomness Cost of Linear Secure Computation : (Invited Presentation)
On the Randomness Cost of Linear Secure Computation : (Invited Presentation)
复制标题
关于线性安全计算的随机性成本：（特邀演讲）
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Shengli Fu
中科院分区：
文献类型：
--
作者：
Yanliang Zhou;Hua Sun;Shengli Fu
我们考虑安全计算的问题，其中K个用户，每个持有一个独立的消息，希望计算的消息上的函数，而不透露任何额外的信息。我们证明了，要安全地计算消息的M个通用线性独立组合（即，对于线性安全计算问题），对于每个消息符号使用$\min\left（\left\lceil\frac{K-M-1}{2}\right\rceil，~M\right）$随机性符号就足够了（即，随机性成本不大于$\min\left（\left\lceil\frac{K-M-1}{2}\right\rceil，~M\right）$）。实现的随机性成本的最优性仍然是开放的。
We consider the problem of secure computation, where K users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We show that to compute M generic linear independent combinations of the messages securely (i.e., for the linear secure computation problem), it suffices to use $\min\left(\left\lceil\frac{K-M-1}{2}\right\rceil,~M\right)$ randomness symbols per message symbol (i.e., the randomness cost is no larger than $\min\left(\left\lceil\frac{K-M-1}{2}\right\rceil,~M\right)$). The optimality of the achieved randomness cost remains open.