Skip to Main content Skip to Navigation
Conference papers

Privacy-Preserving Planarity Testing of Distributed Graphs

Abstract : 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 $${\mathbf F}_2$$F2 is solvable. Our protocol uses a diverse cryptographic toolkit which includes techniques such as homomorphic encryption, oblivious Gaussian elimination, and private set intersection. This is the first time that a solution to this problem is presented.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-01954423
Contributor : Hal Ifip <>
Submitted on : Thursday, December 13, 2018 - 4:04:06 PM
Last modification on : Thursday, February 7, 2019 - 3:37:44 PM
Long-term archiving on: : Thursday, March 14, 2019 - 4:06:47 PM

File

470961_1_En_9_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Guy Barshap, Tamir Tassa. Privacy-Preserving Planarity Testing of Distributed Graphs. 32th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jul 2018, Bergamo, Italy. pp.131-147, ⟨10.1007/978-3-319-95729-6_9⟩. ⟨hal-01954423⟩

Share

Metrics

Record views

74

Files downloads

6