计算机科学
可扩展性
服务器
理论计算机科学
计算
图形
安全两方计算
分布式计算
安全多方计算
协议(科学)
计算机网络
算法
医学
数据库
病理
替代医学
作者
Toshinori Araki,Yoshihiro Furukawa,Kazuma Ohara,Benny Pinkas,Hanan Rosemarin,Hikaru Tsuchida
标识
DOI:10.1145/3460120.3484560
摘要
We present a highly-scalable secure computation of graph algorithms, which hides all information about the topology of the graph or other input values associated with nodes or edges. The setting is where all nodes and edges of the graph are secret-shared between multiple servers, and a secure computation protocol is run between these servers. While the method is general, we demonstrate it in a 3-server setting with an honest majority, with either semi-honest security or full security. A major technical contribution of our work is replacing the usage of secure sort protocols with secure shuffles, which are much more efficient. Full security against malicious behavior is achieved by adding an efficient verification for the shuffle operation, and computing circuits using fully secure protocols. We demonstrate the applicability of this technology by implementing two major algorithms: computing breadth-first search (BFS), which is also useful for contact tracing on private contact graphs, and computing maximal independent set (MIS). We implement both algorithms, with both semi-honest and full security, and run them within seconds on graphs of millions of elements.
科研通智能强力驱动
Strongly Powered by AbleSci AI