Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.02329 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913600002588672 |
|---|---|
| author | Azogagh, Sofiane Birba, Zelma Aubin Desharnais, Josée Gambs, Sébastien Killijian, Marc-Olivier Tawbi, Nadia |
| author_facet | Azogagh, Sofiane Birba, Zelma Aubin Desharnais, Josée Gambs, Sébastien Killijian, Marc-Olivier Tawbi, Nadia |
| contents | Cryptographic approaches, such as secure multiparty computation, can be used to compute in a secure manner the function of a distributed graph without centralizing the data of each participant. However, the output of the protocol itself can leak sensitive information about the structure of the original graph. In particular, in this work we propose an approach by which an adversary observing the result of a private protocol for the computation of the number of common neighbors between all pairs of vertices, can reconstruct the adjacency matrix of the graph. In fact, this can only be done up to co-squareness, a notion we introduce, as two different graphs can have the same matrix of common neighbors. We consider two models of adversary, one who observes the common neighbors matrix only, and a knowledgeable one, that has a partial knowledge of the original graph. Our results demonstrate that secure multiparty protocols are not enough for privacy protection, especially in the context of highly structured data such as graphs. The reconstruction that we propose is interesting in itself from the point of view of graph theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02329 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | GRAND : Graph Reconstruction from potential partial Adjacency and Neighborhood Data Azogagh, Sofiane Birba, Zelma Aubin Desharnais, Josée Gambs, Sébastien Killijian, Marc-Olivier Tawbi, Nadia Cryptography and Security Social and Information Networks Cryptographic approaches, such as secure multiparty computation, can be used to compute in a secure manner the function of a distributed graph without centralizing the data of each participant. However, the output of the protocol itself can leak sensitive information about the structure of the original graph. In particular, in this work we propose an approach by which an adversary observing the result of a private protocol for the computation of the number of common neighbors between all pairs of vertices, can reconstruct the adjacency matrix of the graph. In fact, this can only be done up to co-squareness, a notion we introduce, as two different graphs can have the same matrix of common neighbors. We consider two models of adversary, one who observes the common neighbors matrix only, and a knowledgeable one, that has a partial knowledge of the original graph. Our results demonstrate that secure multiparty protocols are not enough for privacy protection, especially in the context of highly structured data such as graphs. The reconstruction that we propose is interesting in itself from the point of view of graph theory. |
| title | GRAND : Graph Reconstruction from potential partial Adjacency and Neighborhood Data |
| topic | Cryptography and Security Social and Information Networks |
| url | https://arxiv.org/abs/2412.02329 |