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