DEVICES AND METHODS FOR PRIVACY-PRESERVING ROUTING IN COMMUNICATION NETWORKS

Devices and methods for routing data packets in a communication network from a source node to a destination node via one or more intermediate routing nodes in a privacy-preserving manner are disclosed. The source node is configured to concatenate a first routing vector element including a first bit pattern with an initial routing vector defining a bit string, encrypt the concatenation using a selected first encryption key, and replace a portion of the encrypted initial routing vector at a first position by the encrypted first routing vector element. Moreover, the source node is configured to concatenate a second routing vector element, including a second bit pattern and routing information of the destination node, with the modified routing vector, encrypt the concatenation using a selected second encryption key, and replace a portion of the encrypted modified routing vector at a second position by the encrypted second routing vector element. (FIG. 1)

TECHNICAL FIELD

The present disclosure relates to communication networks in general. More specifically, the present disclosure relates to devices and methods for routing data packets in a communication network from a source network node to a destination network node in a privacy-preserving manner.

BACKGROUND

Privacy-preserving network protocols for routing in a communication network have been developed using two main approaches, namely a first approach using a trusted third party to break the relationship between the sender and the receiver, or a second approach using a source routing system in which the privacy of the path described by the source node and taken by the packet in the communication network is protected using cryptographic mechanisms.

In the second approach, the source node determines a path to be taken by the packet it sends to the destination node and includes a description of this path in the packets it sends to the destination node. In order to protect the privacy of the source node and the destination node, it should be impossible for an intermediate routing node along the path to determine what the full path taken by the packets in the communication network is. Rather an intermediate routing node along the path should only be able to determine where the packet comes from (i.e. the previous hop along the path), and where it should send the packet to (i.e. the next hop along the path). To allow the communication between the source node and the destination node to be perfectly private, those intermediate routing nodes, moreover, should not be able to determine the path's length, nor to use any information carried by the packet to correlate packets belonging to the same network flow together.

In light of the above, there is a need for improved devices and methods for routing data packets in a communication network from a source node to a destination node via one or more intermediate routing node in a privacy-preserving manner.

SUMMARY

It is an objective of the present disclosure to provide improved devices and methods for routing data packets in a communication network from a source node to a destination node via one or more intermediate routing nodes in a privacy-preserving manner.

The foregoing and other objectives are achieved by the subject matter of the independent claims. Further implementation forms are apparent from the dependent claims, the description and the figures.

Generally, embodiments disclosed herein allow a source node to encode a path in such a way as to protect information about the path from a rogue observer, while allowing intermediate nodes along the path to decode and lookup routing information they need in a highly efficient fashion. In embodiments disclosed herein this may be implemented in two main stages. In a first stage, public key cryptography may be used by the source node to exchange key material with the intermediate routing nodes forming the path to the destination node. In a second stage, the source node may use this shared key material to build a privacy-protected source routing vector comprising for each of the intermediate routing nodes and the destination node a routing element. This routing vector may have a fixed length and is designed to prevent a given intermediate routing node to derive its position along the path to prevent attacks based on a knowledge of the network topology. Symmetric key cryptography may be used to sequentially encode and/or decode the information carried by the routing elements contained within the routing vector.

More specifically, according to a first aspect a source node is provided for transmitting a data packet to a destination node via one or more intermediate nodes, including a first intermediate node, of a communication network. The communication network may be an IP-based communication network.

The source node comprises a processing circuitry and a communication interface. The processing circuitry is configured to concatenate a first routing vector element including a first bit pattern agreed between the source node and the destination node with an initial routing vector comprising a bit string, to encrypt the concatenation of the first routing vector element and the initial routing vector using a selected first encryption key of a plurality of first candidate encryption keys agreed between the source node and the destination node based on a key derivation mechanism and to replace a portion of the encrypted initial routing vector at a first position of the encrypted initial routing vector by the encrypted first routing vector element for obtaining an encrypted first modified routing vector having the same length as the bit string.

Moreover, the processing circuitry is configured to concatenate a second routing vector element, including a second bit pattern agreed between the source node and the first intermediate node and routing information, e.g. an address or an identifier of the destination node, with the first modified routing vector, encrypt the concatenation of the second routing vector element and the first modified routing vector using a selected second encryption key of a plurality of second candidate encryption keys agreed between the source node and the first intermediate node, and replace a portion of the encrypted first modified routing vector at a second position of the encrypted first modified routing vector by the encrypted second routing vector element for obtaining an encrypted second modified routing vector having the same length as the bit string.

The communication interface is configured to transmit the data packet including the encrypted second modified routing vector towards the first intermediate node.

In a further possible implementation form, the first position of the encrypted initial routing vector and the second position of the encrypted first modified routing vector are random positions selected by the processing circuitry based on a pseudo-random permutation.

In a further possible implementation form, the bit string of the initial routing vector is a random bit string of fixed length.

In a further possible implementation form, the second routing vector element further includes encrypted information about the first position of the encrypted first routing vector element within the encrypted first modified routing vector.

In a further possible implementation form, the data packet further comprises information about the second position of the encrypted second routing vector element within the encrypted second modified routing vector.

In a further possible implementation form, the processing circuitry is further configured to concatenate a third routing vector element, including a third bit pattern agreed between the source node and a second intermediate node and routing information, e.g. an address or an identifier of the first intermediate node, with the second modified routing vector, encrypt the concatenation of the third routing vector element and the second modified routing vector using a selected third encryption key of a plurality of third candidate encryption keys agreed between the source node and the second intermediate node, and replace a portion of the encrypted second modified routing vector at a third random position of the encrypted second modified routing vector by the encrypted third routing vector element for obtaining an encrypted third modified routing vector having the same length as the bit string. The communication interface is further configured to transmit the data packet including the encrypted third modified routing vector towards the second intermediate node of the one or more intermediate nodes of the communication network.

In a further possible implementation form, the processing circuitry is configured to concatenate the first routing vector element with the initial routing vector by prepending the first routing vector element to the initial routing vector and/or the processing circuitry is configured to concatenate the second routing vector element with the first modified routing vector by prepending the second routing vector element to the first modified routing vector.

In a further possible implementation form, the processing circuitry is further configured to encrypt a data packet payload using the selected first encryption key and to further encrypt the encrypted data packet payload using the selected second encryption key.

In a further possible implementation form, for encrypting and decrypting the processing circuitry is configured to use a symmetric key encryption scheme.

In a further possible implementation form, the symmetric key encryption scheme comprises a block cipher, in particular a large block cipher.

In a further possible implementation form, the symmetric key encryption scheme is based on an XOR operation.

In a further possible implementation form, the processing circuitry is configured to generate the first candidate encryption keys using a first key derivation scheme and the second candidate encryption keys using a second key derivation scheme.

In a further possible implementation form, the processing circuitry is further configured to determine the first intermediate node in the communication network using a source routing scheme.

In a further possible implementation form, the first routing vector element further comprises routing information of the destination node.

According to a second aspect a method is provided for transmitting a data packet from a source node to a destination node via one or more intermediate nodes, including a first intermediate node, of a communication network, wherein the method comprises the steps of:concatenating a first routing vector element including a first bit pattern agreed between the source node and the destination node with an initial routing vector comprising a bit string,encrypting the concatenation of the first routing vector element and the initial routing vector using a selected first encryption key of a plurality of first candidate encryption keys agreed between the source node and the destination node based on a key derivation mechanism,replacing a portion of the encrypted initial routing vector at a first position of the encrypted initial routing vector by the encrypted first routing vector element for obtaining an encrypted first modified routing vector having the same length as the bit string;concatenating a second routing vector element, including a second bit pattern agreed between the source node and the first intermediate node and routing information, e.g. an address or an identifier of the destination node, with the first modified routing vector;encrypting the concatenation of the second routing vector element and the first modified routing vector using a selected second encryption key of a plurality of second candidate encryption keys agreed between the source node and the first intermediate node;replacing a portion of the encrypted first modified routing vector at a second position of the encrypted first modified routing vector by the encrypted second routing vector element for obtaining an encrypted second modified routing vector having the same length as the bit string; andtransmitting the data packet including the encrypted second modified routing vector towards the first intermediate node.

The method according to the second aspect can be performed by the source node according to the first aspect. Thus, further features of the method according to the second aspect result directly from the functionality of the source node according to the first aspect as well as its different implementation forms and embodiments described above and below.

According to a third aspect an intermediate node is provided for routing a data packet from a source node to a destination node of a communication network. The intermediate routing node comprises a communication interface configured to receive the data packet from an upstream node of the communication network. Furthermore, the intermediate node comprises a processing circuitry configured to: extract from an encrypted routing vector an encrypted routing vector element, including an encrypted bit pattern and encrypted routing information, e.g. an address or an identifier, of a downstream node; select based on the encrypted bit pattern an encryption key of a plurality of candidate encryption keys; and decrypt the encrypted routing information using the selected key for obtaining the routing information of the downstream node. The communication interface is further configured to send the data packet to the downstream node based on the routing information of the downstream node.

In a further possible implementation form of the third aspect, for encrypting and decrypting the processing circuitry is configured to use a symmetric key encryption scheme.

In a further possible implementation form of the third aspect, the symmetric key encryption scheme comprises a block cipher.

In a further possible implementation form of the third aspect, the symmetric key encryption scheme is based on an XOR operation.

In a further possible implementation form of the third aspect, the upstream node is the source node or a further intermediate node.

In a further possible implementation form of the third aspect, the downstream node is the destination node or a further intermediate node.

In a further possible implementation form of the third aspect, the processing circuitry is further configured to re-encrypt the routing vector element using the selected key.

According to a fourth aspect a method for routing a data packet from a source node via an intermediate node to a destination node of a communication network is provided. The method according to the fourth aspect comprises the steps of:receiving the data packet from an upstream node of the communication network;extracting from an encrypted routing vector an encrypted routing vector element, including an encrypted bit pattern and encrypted routing information, e.g. an address or an identifier of a downstream node;selecting based on the encrypted bit pattern an encryption key of a plurality of candidate encryption keys;decrypting the encrypted routing information using the selected key for obtaining the routing information of the downstream node; andsending the data packet to the downstream node based on the routing information of the downstream node.

The method according to the fourth aspect can be performed by the intermediate node according to the third aspect. Thus, further features of the method according to the fourth aspect result directly from the functionality of the intermediate node according to the third aspect as well as its different implementation forms and embodiments described above and below.

According to a fifth aspect a computer program product is provided, comprising a computer-readable storage medium for storing program code which causes a computer or a processor to perform the method according to the second aspect or the method according to the fourth aspect, when the program code is executed by the computer or the processor.

In the following, identical reference signs refer to identical or at least functionally equivalent features.

DETAILED DESCRIPTION OF THE EMBODIMENTS

In the following description, reference is made to the accompanying figures, which form part of the disclosure, and which show, by way of illustration, specific aspects of embodiments of the present disclosure or specific aspects in which embodiments of the present disclosure may be used. It is understood that embodiments of the present disclosure may be used in other aspects and comprise structural or logical changes not depicted in the figures. The following detailed description, therefore, is not to be taken in a limiting sense, and the scope of the present disclosure is defined by the appended claims.

For instance, it is to be understood that a disclosure in connection with a described method may also hold true for a corresponding device or system configured to perform the method and vice versa. For example, if one or a plurality of specific method steps are described, a corresponding device may include one or a plurality of units, e.g. functional units, to perform the described one or plurality of method steps (e.g. one unit performing the one or plurality of steps, or a plurality of units each performing one or more of the plurality of steps), even if such one or more units are not explicitly described or illustrated in the figures. On the other hand, for example, if a specific apparatus is described based on one or a plurality of units, e.g. functional units, a corresponding method may include one step to perform the functionality of the one or plurality of units (e.g. one step performing the functionality of the one or plurality of units, or a plurality of steps each performing the functionality of one or more of the plurality of units), even if such one or plurality of steps are not explicitly described or illustrated in the figures. Further, it is understood that the features of the various exemplary embodiments and/or aspects described herein may be combined with each other, unless specifically noted otherwise.

FIG.1is a schematic diagram of a communication network100with a plurality of intermediate nodes101a-cfor routing data packets along a communication path from a source node101sto a destination node101dof the communication network100. In an embodiment, the communication network100may be an IP-based communication network100and the plurality of intermediate nodes101a-cmay comprise one or more routers101a-c.

As illustrated inFIG.1, the source node101scomprises a processing circuitry111sand a communication interface113s.The processing circuitry111sof the source node101smay be implemented in hardware and/or software. The hardware may comprise digital circuitry, or both analog and digital circuitry. Digital circuitry may comprise components such as application-specific integrated circuits (ASICs), field-programmable arrays (FPGAs), digital signal processors (DSPs), or general-purpose processors. The communication interface113smay be a wired and/or wireless communication interface configured to exchange data packets, e.g. IP data packets with the other nodes of the communication network100. As illustrated inFIG.1, the source node101smay further comprise a non-transitory memory115sconfigured to store data and executable program code which, when executed by the processing circuitry111scauses the source node101sto perform the functions, operations and methods described herein.

Likewise, the exemplary intermediate routing node101acomprises a processing circuitry111aand a communication interface113a.The processing circuitry111aof the exemplary intermediate routing node101amay be implemented in hardware and/or software. The hardware may comprise digital circuitry, or both analog and digital circuitry. Digital circuitry may comprise components such as application-specific integrated circuits (ASICs), field-programmable arrays (FPGAs), digital signal processors (DSPs), or general-purpose processors. The communication interface113amay be a wired and/or wireless communication interface configured to exchange data packets, e.g. IP data packets with the other nodes of the communication network100. As illustrated inFIG.1, the exemplary intermediate routing node101amay further comprise a non-transitory memory115aconfigured to store data and executable program code which, when executed by the processing circuitry111acauses the exemplary intermediate routing node101ato perform the functions, operations and methods described herein. The other intermediate routing nodes101band101cmay have the same or a similar setup and/or configuration as the intermediate routing node101a.

As will be described in more detail below under further reference toFIGS.2a-dand3a-d,the processing circuitry111sof the source node101sis configured to concatenate a first routing vector element105dincluding a first bit pattern agreed between the source node101sand the destination node101dwith an initial routing vector107comprising a bit string, encrypt the concatenation of the first routing vector element105dand the initial routing vector107using a selected first encryption key103dof a plurality of first candidate encryption keys, and replace a portion of the encrypted initial routing vector107at a first position of the encrypted initial routing vector107by the encrypted first routing vector element105dfor obtaining a first modified routing vector107′.

Moreover, the processing circuitry111sof the source node101sis configured to concatenate a second routing vector element105c,including a second bit pattern agreed between the source node101aand the first intermediate node101cupstream of the destination node101das well as routing information of the destination node101d,with the first modified routing vector107′, encrypt the concatenation of the second routing vector element105cand the first modified routing vector107′ using a selected second encryption key103cof a plurality of second candidate encryption keys, and replace a portion of the encrypted first modified routing vector107′ at a second position of the encrypted first modified routing vector107′ by the encrypted second routing vector element105cfor obtaining a second modified routing vector107″. The same or similar processing steps may be performed for the other intermediate routing nodes101band101a.The communication interface113sof the source node101sis configured to transmit the data packet to the first intermediate routing node101adownstream of the source node101s.

The communication interface113aof the exemplary intermediate routing node101ais configured to receive the data packet from the source node101s.The processing circuitry111aof the exemplary intermediate routing node101ais configured to extract from the encrypted routing vector107″ the encrypted routing vector element105a,including an encrypted bit pattern and encrypted routing information of the next downstream node, i.e. the intermediate routing node101b,select based on the encrypted bit pattern an encryption key103aof a plurality of candidate encryption keys, and decrypt the encrypted routing information using the selected key103afor obtaining the routing information of the next downstream node, i.e. the intermediate routing node101b.The communication interface113aof the exemplary intermediate routing node101ais further configured to send the data packet to the next downstream node, i.e. the intermediate routing node101bbased on the extracted routing information of the intermediate routing node101b.

As will be described in more detail below, embodiments disclosed herein may make use of one or more of four major elements that ensure the fulfillment of advantageous privacy protection properties.

A first mayor element of one or more embodiments disclosed herein is that the information carried by a routing vector107containing a plurality of routing vector elements (or short routing elements)105a-dis protected using a respective shared symmetric key. Advantageously, the use of symmetric key cryptography allows the intermediate routing nodes101a-cto operate at line rate. A respective set of shared candidate keys is negotiated between the source node101aand each intermediate node101a-calong the path. This negotiation of the candidate keys may be based on public key cryptography. Once this shared key is agreed upon, a set of temporary keys can be derived from this master key to avoid the use of public key cryptography while ensuring a key rotation that prevents packets to be associated in a same data flow.

A second mayor element of one or more embodiments disclosed herein is that the routing vector107containing the routing elements may have a fixed size as the corresponding data packet travels along the path from the source node101sto the destination node101d.This allows preventing an external observer intercepting a data packet to derive any hints about the source node101sand the destination node101dbased on the length of the routing vector107.

A third mayor element of one or more embodiments disclosed herein is that the position of the routing element for a given intermediate node101a-cmay be randomly permuted within the routing vector107so that the respective intermediate node101a-ccannot infer based on the position of its routing element within the routing vector107any information about how many hops it is away from the source node101sor the destination node101d.This may prevent deanonymization attacks using topological information to diminish the anonymity set's size for either the source node101sor the destination node101d.

A fourth mayor element of one or more embodiments disclosed herein is that the routing vector107is generated and processed in such a way that it can be processed at each intermediate node101a-cwithout having to perform a lot of rewrite operations.

As will be appreciated, in an embodiment, the relevant part of the routing vector may not be the first bytes dedicated to carrying a first routing element, but due to the random permutation a different set of bytes, whose position is defined a header element of the data packet. In an embodiment, the symmetric encryption operation for encrypting/decrypting the respective routing element of the routing vector at an intermediate node101a-cmay be an XOR operation with the respective selected candidate key103a-d.This processing is very quick and may ensure that the data packet can be processed at line rate. In an embodiment, the encryption operation may be performed after prepending the routing vector107with the routing element150a-cof an intermediate routing node101a-dand then using the selected symmetric key established with that node to encrypt the concatenation. During a further step, the prepended routing element is cut and put in the randomly selected position within the routing vector107. As will be appreciated, this “encrypt, then cut and paste”-approach for generating the routing vector107avoids having information in the clear during the packet relaying phase, while avoiding the need to rewrite the whole routing vector107. This allows preventing packet correlation attacks allowing an attacker to associate packets to a specific flow of data packets.

By combing one or more of the four mayor elements described above, embodiments disclosed herein may protect the privacy of a path through the communication network100at the network layer without having to involve a trusted third party. Source routing and recursive routing vector encryption may be used so that a given intermediate node101a-ccan only access routing information that is relevant to the respective node, and an external observer is unable to correlate packets belonging to the same flow together.

In the following, the generation of the routing vector107by the source node101sand the relaying of the routing vector107by the intermediate routing nodes101a-cto the destination node101dfor the exemplary path shown inFIG.1is described in more detail.

In an embodiment, the routing vector107may have a fixed size in that the length, i.e. the number of bits/bytes of the routing vector107stays constant as the data packet containing the routing vector107travels from the source node101avia the intermediate routing nodes101a-cto the destination node101d.In an embodiment, the routing vector107may contain MAX_PATH_LENGTH elements of size SEGMENT_LENGTH bytes containing in particular the routing information that will be used by a given intermediate node101a-cfor routing the data packet to the destination node101d.

The source node101shas exchanged shared key material with the intermediate nodes101a-cand the destination node101d.In an embodiment, this shared key material may comprise a respective shared master key as well as a respective synchronized key derivation scheme and its associated parameters. In an embodiment, for encrypting/decrypting the source node101s,the intermediate routing nodes101a-cand the destination node101dmay use a large block symmetric key encryption scheme Enc( . . . ) such that Enc(Enc(p, kSX), kSX)=p.

FIGS.2a-dand3a-dillustrate different stages of the generation of the data packet including the routing vector107by the source node101saccording to an embodiment. In a preliminary stage, the source node101smay determine based on a source routing scheme a path to the destination node101dthrough the communication network100, which in the exemplary embodiment shown inFIGS.1,2a-dand3a-dincludes the intermediary routing nodes101a-c.For encoding information about this path in the data packet the processing circuitry111sof the source node101sobtains the addresses for the intermediate routing nodes101a-cand the destination node101dalong this path, i.e. A_addr, B_addr, C_addr and D_addr. Thereafter, the processing circuitry111sof the source node101smay initialize the routing vector107by generating a random byte string of length MAX_PATH_LENGTH×SEGMENT_LENGTH. As will be appreciated, for this embodiment the initialized routing vector107defines MAX_PATH_LENGTH slots for the routing elements105a-d,wherein each slot, i.e. routing element105a-dcomprises SEGMENT_LENGTH bits. In an embodiment, the processing circuitry111sof the source node101sis configured to randomize the location of the plurality of routing elements105a-dwithin the routing vector107based on a pseudo-random permutation over the MAX_PATH_LENGTH slots available of the routing vector107. As will be described in more detail below, in case the next downstream node is another intermediate routing node each routing element105a-d(referred to as “Seg. A”, “Seg. B”, “Seg. C” and “Seg. D” inFIG.2) may comprise in addition to the respective encrypted bit pattern information, e.g. an address of the next downstream intermediate node101a-cas well as a pointer to the location of the routing element105a-dof the next downstream intermediate node101a-cwithin the routing vector107. In an embodiment, because the destination node101sis the last node along the path the routing element105dfor the destination node101d(“Seg. D” inFIG.2) may only comprise the encrypted bit pattern for identifying the encryption key. In a further embodiment, the routing element105dfor the destination node101dmay further comprise an address of the destination node101dor a default address indicative of the destination node101dbeing the destination of the data packet.

Having performed the operations described above the following elements are available to source node101s:a list of the intermediate routing nodes101a-cdefining the path to the destination node101d,the routing elements105a-dfor the intermediate routing nodes101a-cand the destination node101das well as the information about the random locations of the respective routing elements105a-dwithin the routing vector107. Based on this information the processing circuitry111sof the source node101smay generate the complete routing vector107starting with the routing element105dfor the destination node101d,as illustrated inFIGS.2a.

As illustrated inFIG.2b, the processing circuitry111sof the source node101sprepends the routing element105d(i.e. “Seg. D”) to the initial routing vector107, e.g. the randomized bit string107. In a next stage, the processing circuitry111sof the source node101sobtains an encryption key based directly or indirectly on the shared key kSDbetween the source node101sand the destination node101d.In an embodiment, the processing circuitry111sof the source node101smay select the encryption key from a plurality of encryption key candidates that are based on the shared key kSD. In an embodiment, the source node101sand the destination node101dmay use the same key derivation scheme for generating the plurality of encryption key candidates based on the shared key kSD. In an embodiment, the encryption key may have the length (MAX_PATH_LENGTH+1)×SEGMENT_LENGTH, i.e. the same length (number of bits) as the concatenation of the routing element105d(i.e. “Seg. D”) with the initial routing vector107, e.g. the randomized bit string107. In such an embodiment, the processing circuitry111sof the source node101smay encrypt the concatenation of the routing element105d(i.e. “Seg. D”) with the initial routing vector107by performing an XOR operation of the selected encryption key with the concatenation of the routing element105d(i.e. “Seg. D”) with the initial routing vector107. In an embodiment, the processing circuitry111sof the source node101smay use for the encryption a block cipher witch a large block size, such as Lioness which builds on top of AES-128. In this block cipher, the encryption is a XOR operation with a large vector built using the selected key. As will be appreciated, for such a cipher based on an XOR operation, encryption and decryption are symmetric, and the position of the encrypted elements plays a role in the encryption's correctness.

After the concatenation of the routing element105d(i.e. “Seg. D”) with the initial routing vector107of length (MAX_PATH_LENGTH+1)×SEGMENT_LENGTH has been encrypted, the processing circuitry111sof the source node101sis configured to cut the encrypted routing element105d(i.e. “Seg. D”), i.e. the first SEGMENT_LENGTH bits of the encrypted string and paste this byte string at the location within the routing vector107predetermined by the random permutation, as illustrated inFIGS.2cand2d.

As will be appreciated fromFIGS.3a-d,the same processing steps are performed by the processing circuitry111sof the source node101sfor including the routing elements of the intermediate routing nodes101a-c.Thus, the source node101scontinues the process described above with respect to the destination node101dfirst for the first intermediate node upstream of the destination node101d,namely intermediate node101c,then for intermediate node101band finally for intermediate node101a.As a result of this sequential generation process implemented by the processing circuitry111sof the source node101sthe sequentially-encrypted routing elements vector107″ illustrated inFIG.4is obtained, which is send via the communication interface113sof the source node101sto the first downstream intermediate routing node101a.

FIGS.5a-dillustrate in more detail how the data packet shown inFIG.4is processed and relayed by the exemplary intermediate routing node101a.In an embodiment, the header of the data packet carrying the routing elements vector107″ further contains a pointer to the encrypted routing element105aof the intermediate routing node101a,i.e. Enc(Seg. A, kSA). Based on the encrypted bit pattern included in the encrypted routing element105athe processing circuitry111aof the intermediate routing node101ais configured to determine the key kSAfor decrypting the encrypted routing element105aof the intermediate routing node101a,i.e. Enc(Seg. A, kSA). Once decrypted, the processing circuitry is configured to extract the routing information of the next downstream node from the routing element105a,e.g. an address of the routing node101bas well as information about the random location of the routing element105bof the intermediate routing node101bwithin the routing vector107″. In an embodiment, the processing circuitry may be configured to re-encrypt its routing element105awithin the routing vector107″.

In an embodiment, the processing circuitry111aof the intermediate routing node101ais configured to generate a key stream of length (MAX_PATH_LENGTH+1)×SEGMENT_LENGTH based on the key kSAand to use the first SEGMENT_LENGTH bits of the key stream to decrypt (for instance by an XOR operation with the key stream) the encrypted routing element105a,i.e. Enc(Seg. A, kSA) and to retrieve the routing information it needs for routing the data packet, namely the address of the next intermediate routing node101bas well as the pointer to the slot in the routing vector107″ associated with this next node. In an embodiment, the processing circuitry111aof the intermediate routing node101amay insert the pointer to the slot in the routing vector107″ associated with the next downstream node, i.e. the intermediate routing node101bas unencrypted metadata in the header of the data packet. Then the processing circuitry111aof the intermediate routing node101ais configured to re-encrypt the whole routing vector107″, for instance, by using the trailing MAX_PATH_LENGTH×SEGMENT_LENGTH bits of the key stream generated on the basis of the key kSA. This hides the information contained in the routing element105a(i.e. Seg. A) and removes the kSAencryption layer from the remaining of the routing vector107″. The such processed data packet is forward to the next downstream intermediate routing node101b.The key kSAor its derivative can then be deleted in order to prevent it from being retrieved or reused. In a further embodiment, the key kSAmay be kept, if forward secrecy is not a threat that is considered serious.

As will be appreciated, at the intermediate routing nodes101band101cthe same steps may be performed as described above in the context of the intermediate routing node101a.In this way the data packet and the routing vector107″ contained therein is further processed and relayed to the destination node101d.Like the intermediate routing nodes101a-cthe destination node101dmay be configured to retrieve the routing element105dfrom the routing vector107″. In an embodiment, the routing element105dof the destination node101dmay only comprise the encrypted bit pattern for identifying the encryption key used by the source node101sfor encrypting the packet payload. In a further embodiment, the routing element105dfor the destination node101dmay further comprise its own address (or a default address) indicating to the destination node101dthat it is the intended destination of the data packet.

FIG.6is a flow diagram illustrating a method600for transmitting a data packet from a source node to a destination node via one or more intermediate nodes, including a first intermediate node, in a communication network according to an embodiment.

The method600comprises a step of concatenating601a first routing vector element including a first bit pattern agreed between the source node and the destination node with an initial routing vector comprising a bit string.

The method600further comprises a step of encrypting603the concatenation of the first routing vector element and the initial routing vector using a selected first encryption key of a plurality of first candidate encryption keys.

The method600further comprises a step of replacing605a portion of the encrypted initial routing vector at a first position of the encrypted initial routing vector by the encrypted first routing vector element for obtaining a first modified routing vector.

The method600further comprises a step of concatenating607a second routing vector element, including a second bit pattern agreed between the source node and the first intermediate node and routing information of the destination node, with the first modified routing vector.

The method600further comprises a step of encrypting609the concatenation of the second routing vector element and the first modified routing vector using a selected second encryption key of a plurality of second candidate encryption keys.

The method600further comprises a step of replacing611a portion of the encrypted first modified routing vector at a second position of the encrypted first modified routing vector by the encrypted second routing vector element for obtaining a second modified routing vector.

The method600further comprises a step of transmitting613the data packet including the second modified routing vector towards the first intermediate node.

The method600can be performed by the source node101saccording to an embodiment. Thus, further features of the method600result directly from the functionality of the source node101aas well as its different embodiments described above and below.

FIG.7is a flow diagram illustrating a method700for routing a data packet from a source node via an intermediate node to a destination node of a communication network according to an embodiment.

The method700comprises a step of receiving701the data packet from an upstream node of the communication network.

The method700further comprises a step of extracting703from an encrypted routing vector an encrypted routing vector element, including an encrypted bit pattern and encrypted routing information of a downstream node.

The method700further comprises a step of selecting705based on the encrypted bit pattern an encryption key of a plurality of candidate encryption keys.

The method700further comprises a step of decrypting707the encrypted routing information using the selected key for obtaining the routing information of the downstream node.

The method700further comprises a step of sending709the data packet to the downstream node based on the routing information of the downstream node.

The method700can be performed by one of the intermediate routing nodes101a-caccording to an embodiment. Thus, further features of the method700result directly from the functionality of the intermediate routing nodes101a-cas well as their different embodiments described above and below.

Embodiments disclosed herein make use of a privacy-preserving routing element vector107to be used in the anonymous source routing communication network100. The privacy of the information stored in the routing element vector107may be ensured by the fixed size of the vector107to prevent an external observer to determine the path's length. The in-vector location of each routing element105a-cmay be given by a pseudo-random permutation to prevent an observer from determining the position of a node on the path. A shared symmetric key may be used to encode the routing information elements. The shared symmetric key may be a one-time key derived from a master key to ensure packet flow unlinkability. The above described prepend, encrypt then cut and paste approach allows an intermediate node101a-cprocessing the routing element vector107to have to rewrite the whole structure, thus making packet processing faster.

The person skilled in the art will understand that the “blocks” (“units”) of the various figures (method and apparatus) represent or describe functionalities of embodiments of the present disclosure (rather than necessarily individual “units” in hardware or software) and thus describe equally functions or features of apparatus embodiments as well as method embodiments (unit=step).

In addition, functional units in the embodiments disclosed herein may be integrated into one processing unit, or each of the units may exist alone physically, or two or more units are integrated into one unit.