Secure Virtual Network Embedding Through Fully Homomorphic Encryption

In this paper, we show how various forms of Fully Homomorphic Encryption can be used to solve the problem of embedding a virtual network onto multiple substrate networks where the substrate network providers do not wish to reveal information about their inner network structures. We implement a basic Greedy Shortest Paths Virtual Network Embedding algorithm and show that while node mapping is relatively efficient, edge mapping of a fully encrypted substrate network description using Dijkstra’s Shortest Paths algorithm is heavily dependent upon the amount of information we are willing to reveal to the program implementing the algorithm. We provide runtime performance metrics for various parts of the embedding problem and show that through the use of interactive comparison, where the result of each encrypted comparison operation are jointly decrypted by all network providers, we can significantly improve the runtime of edge mapping to the point where it is of practical value.