Privacy-Preserving Planarity Testing of Distributed Graphs

作     者：Barshap, Guy Tassa, Tamir 

作者机构：Open Univ Israel Tel Aviv Israel Ben Gurion Univ Negev Beer Sheva Israel 

出 版 物：《TRANSACTIONS ON DATA PRIVACY》 (数据保密汇刊)

年 卷 期：2019年第12卷第2期

页      面：117-144页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

主　　题：secure multiparty computation privacy-preserving distributed computations distributed graphs graph planarity 

摘      要：We study the problem of privacy-preserving planarity testing of distributed graphs. The setting involves several parties that hold private graphs on the same set of vertices, and an external mediator that helps with performing the computations. Their goal is to test whether the union of their private graphs is planar, but in doing so each party wishes to deny from his peers any information on his own private edge set beyond what is implied by the final output of the computation. We present a privacy-preserving protocol for that purpose which is based on the Hanani-Tutte theorem. That theorem enables translating the planarity question into the question of whether a specific system of linear equations over the field F-2 is solvable. Our protocol uses a diverse cryptographic toolkit which includes techniques such as homomorphic encryption, oblivious Gaussian elimination, and private set intersection.