Constraint-Based Privacy Preserving-Path Computation Element

Constraint-Based Privacy Preserving-Path Computation Element

Hamid Hajaje, Mouhcine Guennoun, Zine El Abidine Guennoun
Copyright: © 2019 |Pages: 32
DOI: 10.4018/IJSST.2019070101
(Individual Articles)
No Current Special Offers


Information privacy and protection is fundamental in the context of path computation. When a path computation client (PCC) requests the shortest path between two nodes from a path computation element (PCE), it desires to do so while protecting the sensitive information carried by the query as well as the overall topology of the network. The authors provide a novel framework to compute the shortest path, between a source and a destination, subject to a constraint, represented in the case by a required minimum bandwidth, while preserving the privacy of both client and server. By employing a secure homomorphic encryption scheme, the PCE can blindly compute the path while being oblivious to the content of the encrypted queries. The output of the PCE computation is an encrypted path that is only decipherable by its original secret key. The implementation using the homomorphic scheme over the integers from Van Dijk, Gentry, Halevi, and Vaikuntanathan (DGHV) shows promising results that the authors analyze in detail throughout this paper.
Article Preview


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 IJSST.2019070101.m01, meaning the set IJSST.2019070101.m02 equipped with addition modulo two and usual multiplication and the set of ciphertext is any ring IJSST.2019070101.m03;

  • 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.

Complete Article List

Search this Journal:
Volume 10: 1 Issue (2023): Forthcoming, Available for Pre-Order
Volume 9: 2 Issues (2022): 1 Released, 1 Forthcoming
Volume 8: 2 Issues (2021)
Volume 7: 2 Issues (2020)
Volume 6: 2 Issues (2019)
View Complete Journal Contents Listing