Workshops Archive

Towards Distributed-Memory All-Pairs Reachability over Homomorphically Encrypted Graphs


Workshop: 5th International Workshop on Cyber Security in High Performance Computing

Authors: Charis Hulu (University of Illinois Chicago) and Anrin Chakraborti and Sidharth Kumar (University of Illinois at Chicago)

Abstract: Transitive closure determines reachability between all pairs of vertices in a directed graph. For encrypted graphs, this computation requires many expensive ciphertext operations. This makes single-node execution slow even for small matrices.

We implement transitive closure (all-pairs reachability) for BGV-encrypted graphs on distributed memory systems. The implementation stores matrix rows and columns in separate ciphertexts. Each output entry is computed from one row ciphertext and one column ciphertext. We distribute these computations over a two-dimensional MPI process grid. The output remains distributed and is reused in the next transitive-closure step.

We evaluate the implementation with up to 1,024 MPI ranks and compare against a single-node baseline with 32 OpenMP threads. At N=16, the distributed implementation achieves a 5.66 times speedup over the single-node baseline.


Back to 5th International Workshop on Cyber Security in High Performance Computing Archive Listing

Back to Full Workshop Archive Listing