BFS Implementation using EVA

Homomorphic BFS implementation is quite similar to the naive BFS that we have learned in data structures and algorithms courses. Only difference is that, since we are not able to check whether the given input is equal to some value without decryption by the nature, it is a challenging task to do branching according to the result of the mathematical operations in the program that runs our algorithm on the encrypted data.

BFS Algorithm

Algorithm's steps can be seen from the list below:

Step 1: Choose a node randomly, to start traversing.
Step 2: Visit its adjacent unvisited node.
Step 3: Mark it as visited in the visited array. Step 4: Insert the visited node into the queue.
Step 5: If there is no adjacent node, remove the first node from the queue.
Step 6: Repeat the above steps until the queue is empty.

Implementation

In this task, we have two sides: client and server. Client is a trusted entity. It can encrypt and decrypt data with it's key.. On the other hand, server is unable to decrypt data since it doesn't have key.

Adjacency matrix has been used. During iterations, in order to decide which nodes are reachable from the current node, the actual reachable nodes list is kept in the trusted entity. Data that contains unvisited nodes which are not in the queue are sent to the client at each pass. Then client takes this list and masks to decide which nodes are actually reachable. During next iteration, encryption algorithm uses this to iterate on the queue with new elements.