Constraint-Based Privacy Preserving-Path Computation Element

Introduction

Path computation element (PCE) is a dedicated real time application or router that is responsible for computing paths for multiprotocol label switching (MPLS) label switched path (LSP) from the head end, i.e. source node, to the tail end, i.e. destination node. PCE can use a suitable algorithm to compute paths subject to one or more constraints such as latency, bandwidth, and optimization criteria such as cumulative path cost. The scope of computed path can be intra-area, inter-area, or inter-AS (Autonomous System).

In a typical scenario, a path computation client (PCC) sends a request to PCE with the necessary information for path computation. The request contains the source, destination addresses, metric, and additional constraints to be used in the path computation process. Path computation element protocol (PCEP) is the de-facto IETF standard for PCC-PCE communication. Upon reception of a request, PCE computes the path using the information in its topology database to determine the optimal path. The resulting path is sent back to PCC which establishes the LSP ‎‎(Dhody & Zhang 2017).

Figure 1 represents a network containing a number of PCCs and a PCE where the communication between each PCC and the PCE takes place using PCEP.

Figure 1.

PCC-PCE communication

The current path computation model requires that PCE to have the knowledge about source and destination addresses/identities, metric type, and once computed, to have the knowledge of the path including the path hops (specified in the form of IP address, MPLS label, etc.), as well as the value of the cost associated with the computed path. There are scenarios in which trusted relationship between PCC and PCE does not exist, e.g., PCC and PCE belong to different service providers or administrative domains, in cloud computing services offering path computation as a service. Thus, there is a need for a new type of PCE which is capable of computing paths while preserving the privacy of PCCs, source and destination addresses/identities, as well as computed paths.

The main idea is to build a PCE capable of finding the k shortest paths verifying the required constraint (a minimal bandwidth in our case) from a source to a destination without having the knowledge of the clear text value of neither the source nor the destination. In such a model, PCC encrypts the source and destination of the path using a symmetric cryptosystem with its secret key (sk). PCC sends the resulting encrypted values to PCE. In our model, PCE applies a blind extraction technique that finds the optimal path from the source to the destination without the need to decrypt the ciphertexts of the source and destination. The resulting path contains encrypted hops under the same secret key sk. PCE sends back the encrypted path to PCC which can use its secret key to decrypt the path hops.

The encryption scheme needed to build the oblivious PCE should have the property of being able to perform addition and multiplication operations on cipher-texts since both these operations are taken advantage of in our protocol calculations. Encryption schemes supporting both addition and multiplication over ciphertexts are referred to in literature as homomorphic encryption schemes. There are two types of homomorphic schemes: somewhat and fully homomorphic. The first type can perform limited number of operations on the ciphertexts, while the latter can perform arbitrary number of operations on ciphertexts, but it has the overhead of a computationally expensive bootstrapping technique needed to refresh the ciphertext.

Our model is flexible with regard to the used cryptosystem in the sense that it does not require a specific cryptosystem by itself. It rather requires the used cryptosystem to have the following properties:

• •

  The set of plaintext messages is the ring , meaning the set equipped with addition modulo two and usual multiplication and the set of ciphertext is any ring ;

• •

  The cryptosystem is fully homomorphic, or at least somewhat homomorphic but with parameters enabling the execution of the shortest path circuit while keeping the noise sufficiently small to guarantee decryption correctness. This property is known as Leveled homomorphic encryption.