Publications

2025

1. GRAND : Graph Reconstruction from Potential Partial Adjacency and Neighborhood Data

   Sofiane Azogagh, Zelma Aubin Birba, Josée Desharnais, and 3 more authors

   In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, 2025

   Abs PDF Poster

   Cryptographic approaches, such as secure multiparty computation, can be used to securely compute a function of a distributed graph without centralizing the data of each participant. However, the output of the protocol can leak sensitive information about the structure of the original graph. In particular, 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. To realize this, we consider two adversary models, one who observes the common neighbors matrix only and a more informed one that has partial knowledge of the original graph. Our results demonstrate that, from their common neighbors matrix, graphs can be reconstructed with high accuracy (up to co-squareness). The proposed reconstruction is also interesting in itself from the point of view of graph theory.

2. Oblivious (Un)Learning of Extremely Randomized Trees

   Sofiane Azogagh, Zelma Aubin Birba, Sébastien Gambs, and 1 more author

   2025

   Abs PDF

   While the use of homomorphic encryption (HE) for encrypted inference has received considerable attention, its application for the training of machine learning (ML) models remains comparatively underexplored, primarily due to the high computational overhead traditionally associated with fully homomorphic encryption (FHE). In this work, we address this challenge by leveraging the inherent connection between inference and training in the context of Extremely Randomized Trees (ERT), thereby enabling efficient training directly over encrypted data. More precisely, we instantiate this approach by the training of ERT within the TFHE framework. Our implementation demonstrates that it is possible to train ERTs on encrypted datasets with a runtime significantly lower than current state-of-the-art methods for training Random Forests in the encrypted domain while achieving comparable predictive accuracy. This result highlights a promising direction for practical privacy-preserving machine learning using FHE. Our second main contribution consists in leveraging the properties of ERTs to create the first ML model that enables private unlearning. This approach makes the unlearning process indistinguishable from training, thus allowing clients to conceal the true nature of the operations being conducted on the model.

2024

1. Crypto’Graph: Leveraging Privacy-Preserving Distributed Link Prediction for Robust Graph Learning

   Sofiane Azogagh, Zelma Aubin Birba, Sébastien Gambs, and 1 more author

   In Proceedings of the Fourteenth ACM Conference on Data and Application Security and Privacy, 2024

   Abs PDF Code

   Graphs are a widely used data structure for collecting and analyzing relational data. However, when the graph structure is distributed across several parties, its analysis is challenging. In particular, due to the sensitivity of the data each party might want to keep their partial knowledge of the graph private, while still be willing to collaborate with the other parties for tasks of mutual benefit, such as data curation or the removal of poisoned data. To address this challenge, we propose Crypto’Graph, an efficient protocol for privacy-preserving link prediction on distributed graphs. More precisely, it allows parties partially sharing a graph with distributed links to infer the likelihood of formation of new links in the future. Through the use of cryptographic primitives, Crypto’Graph is able to compute the likelihood of these new links on the joint network without revealing the structure of the private graph of each party, even though they know the number of nodes they have, since they share the same graph in terms of nodes but not the same links. Crypto’Graph improves on previous works by enabling the computation of a diverse set of similarity metrics in parallel without any additional cost. The use of Crypto’Graph is illustrated for defense against graph poisoning attacks, in which potential adversarial links are identified without compromising the privacy of the graphs of individual parties. The effectiveness of Crypto’Graph in mitigating graph poisoning attacks and achieving high prediction accuracy on a node classification task using graph neural networks is demonstrated through extensive experimentation on two real-world datasets.

2. RevoLUT : Rust Efficient Versatile Oblivious Look-Up-Tables

   Sofiane Azogagh, Zelma Aubin Birba, Marc-Olivier Killijian, and 2 more authors

   2024

   Abs PDF

   In this paper we present RevoLUT, a library implemented in Rust that reimagines the use of Look-Up-Tables (LUT) beyond their conventional role in function encoding, as commonly used in TFHE’s programmable boostrapping. Instead, RevoLUT leverages LUTs as first class objects, enabling efficient oblivious operations such as array access, elements sorting and permutation directly within the table. This approach supports oblivious algortithm, providing a secure, privacy-preserving solution for handling sensitive data in various applications.

3. POMS : Proxy Offloading for Multicloud Storage with Keyword Search

   Adam Oumar Abdel-Rahman, Sofiane Azogagh, Zelma Aubin Birba, and 1 more author

   2024

   Abs PDF

   Cloud storage offers convenient data access and sharing, but security concerns remain. Existing secure cloud storage solutions often lack essential features like data integrity, multi-cloud support, user-friendly file sharing, and efficient search. This paper proposes a novel secure cloud storage system that addresses these limitations. Our system uses distributed storage and attribute-based encryption to enhance data availability, access control, and user experience. It also enables private and efficient file search and data retrievability verification. This approach overcomes the trade-offs present in prior work, offering a secure and user-friendly solution for cloud data management.