Checking chordality on homomorphically encrypted graphs
This work addresses a specific problem for practitioners in cryptography and graph theory by enabling chordality checks on encrypted data, but it is incremental as it adapts an existing method rather than introducing a new one.
The paper tackles the problem of checking chordality on homomorphically encrypted graphs by providing an easy-to-implement interactive algorithm, which is a refactoring of an existing method to run on encrypted adjacency matrices, though no concrete performance numbers are reported.
The breakthrough of achieving fully homomorphic encryption sparked enormous studies on where and how to apply homomorphic encryption schemes so that operations can be performed on encrypted data without the secret key while still obtaining the correct outputs. Due to the computational cost, inflated ciphertext size and limited arithmetic operations that are allowed in most encryption schemes, feasible applications of homomorphic encryption are few. While theorists are working on the mathematical and cryptographical foundations of homomorphic encryption in order to overcome the current limitations, practitioners are also re-designing queries and algorithms to adapt the functionalities of the current encryption schemes. As an initial study on working with homomorphically encrypted graphs, this paper provides an easy-to-implement interactive algorithm to check whether or not a homomorphically encrypted graph is chordal. This algorithm is simply a refactoring of a current method to run on the encrypted adjacency matrices.