XOR-Embedded Random Linear Network Coding

Ⅰ. Introduction

Data confidentiality is a significant burden for businesses of all sizes. However, not all data are open to the same level of risk^[1]. For instance, low-risk environ- ments, publicly available files, non-sensitive data, and temporary or disposable files may not require a high degree of security protection^[1,2]. As such, it is important for organizations to develop low-risk data security guidelines that balance the level of protection with the associated costs and resources required. Also, in situations where stronger encryption methods may not be practical to implement due to computational or bandwidth limitations, Network Coding can provide some level of confidentiality.

XOR network coding efficiently transmits data by applying the XOR operation to mix packets, enhancing multicast data transmission^[3] and offering some protection against eavesdropping by complicating signal decryption^[4]. Random linear network coding (RLNC) extends this by using random coefficients, increasing data confidentiality as eavesdroppers need exact coefficients to decode^[5]. In RLNC, these random coefficients are elements chosen from a finite field, typically denoted as GF(q), where ‘q’ represents the field size, equating to [TeX:] $$2^h$$. For instance, in GF(2), 2 elements are available, any of which can be coefficients in the encoding process. RLNC divides data into n packets, encoding them with random finite field coefficients. It transmits at least n packets, formed by linearly combining original packets. The receiver, upon collecting k (k ≥n) packets, constructs a matrix from the coefficients to decode data by solving linear equations. RLNC secures data through complex mathematics, using random coefficients and linear independence to deter unauthorized decoding and require eavesdroppers to capture many independent packets to decode the data. It also offers error resilience, enhancing networksecurity and reducing overhead with minimal spectrum usage. Refer to Fig. 1. for a basic description of RLNC.

Some reported works^[6-9] collectively explore advanced network coding techniques like RLNC using a Vandermonde matrix to create the coding vectors (RL-NCV), Secure Practical Network Coding (SPOC), and Fulcrum network coding (FNC). These methods enhance data confidentiality and network performance by integrating cryptographic methods, optimizing encoding mechanisms, and reducing overhead, each contributing uniquely to improved security in network communications. Additionally, recent studies^[10,11] have extensively compared RLNC and XOR network coding, with evidence favoring RLNC, especially in networks with packet losses or larger sizes. However, to the best of our knowledge, no existing scenarios have incorporated both RLNC and XOR network coding to enhance data confidentiality against eavesdroppers while maintaining reliability and minimizing encoding latency.

Thus, in this paper, we introduce XOR-embedded network coding (XORE-NC), an innovative technique. It uses a two-stage encoding process, first applying systematic XOR network coding to packets in specified generation-size blocks. At this stage, XOR-encoded packets from each generation are woven into a new combined set, forming the outer code. These combined packets are then prepared for the second stage-RLNC inner encoding with GF(2) coefficients-enhancing the packets for robust transmission. This stage can dynamically adjust the encoding to make up for any lost or corrupted packets. Summarily, our model merges XOR and RLNC encoding to boost data transmission robustness and efficiency, and its outer code enhances RLNC inherent privacy, the primary focus of this paper. Results show that XORE-NC enhances reliability, reduces encoding delay, and lowers latency and throughput versus traditional RLNC, offering a viable solution for data confidentiality. Despite challenges with decoding delay, XORE-NC remains a promising approach for enhancing data security with efficient transmission in communication systems.

Ⅱ. Related Studies

Additional techniques like permutation encryption can be used to increase data confidentiality, even in cases of packet loss or corruption^[6]. While^[7] primarily focuses on evaluating and enhancing network performance parameters like throughput and delay for RLNC and RLNCV compared to traditional Store and Forward techniques, RLNCV also has significant implications for security. Its unique encoding properties, particularly the encryption of coding coefficients and the need for only a single element for decoding^[7], make it a potent tool for enhancing data confidentiality and resistance to eavesdropping in network communications.

The SPOC security framework, as discussed in [8], aims to enhance network coding inherent security through integration with standard cryptographic techniques. It modifies RLNC-based protocols at the source and receiver nodes, using two types of coefficients: unlocked coefficients (derived from the identity matrix for each coded packet) and locked coefficients (used for encoding and decoding but encrypted with keys available at the destination). This method allows for encrypting only the locked coefficients, as opposed to encrypting the entire data, thereby optimizing security and encryption efficiency.

Fulcrum network coding (FNC) framework employs a two-stage encoding process that enhances efficiency and flexibility by initially transforming n source packets into n + r outer coded packets for error correction using coefficients from GF ([TeX:] $$2^8$$) or GF (216), and then encoding them in GF ([TeX:] $$2^{16}$$) independently, enhances coding flexibility network throughput, and adds complexity to encoded data for increased security in diverse communication environments^[9].

FNC can contribute to security in the context of SPOC by offering a simplway to implement SPOC’s concepts[9]. Specifically, in Fulcrum, the mapping of the outer decoder can act as a secret key (or part of it) between the source and destinations. This key, unlike in traditional SPOC implementations, does not need to be transmitted over the network along with the coded packets. By avoiding the transmission of this key, FNC reduces the overhead typically associated with SPOC, which often involves sending additional coding coefficients with each packet. This makes FNC a more efficient and potentially more secure alternative in the realm of practical network coding. However, the extra r redundant packets incurred by FNC, also increases the packet overhead when compared to traditional RLNC.

Thus, we propose XORE-NC, which maintains packet overhead equal to RLNC. Consider the example of XORE-NC in Section III, as simplified in Fig. 2. Compared to traditional RLNC, which encodes N original packets directly without adding overhead, FNC introduces additional r packets, increasing the total to N + r and thereby adding overhead. SPOC may also introduce overhead through the encryption of coefficients. In contrast, XORE-NC aligns with traditional RLNC in terms of overhead. XORE-NC’s outer code, once RLNC encoded, keeps the original count N. Therefore, while FNC and SPOC offer enhanced security features, XORE-NC can provide security improvement without the additional overhead, making it potentially the most efficient scheme compared to traditional RLNC. Consequently, our XORE-NC model positively impacts transmission efficiency by reducing latency and encoding time while enhancing throughput. Table 1 gives an overview the above schemes.

Ⅲ. XORE-NC: Methodology

Our approach allows for the transmission of multiple generations of packets in pairs when the total number of packets to be transmitted is even while increasing data confidentiality. Otherwise, when there is an odd number of packets, the last block of packets that cannot be paired with another is sent using conventional RLNC. This approach, under small generation sizes, performs better in terms of minimizing latency, encoding latency, and data reliability.

As illustrated in Fig. 3, two instances highlight the advantages of XOR-embedded packets in thwarting eavesdroppers. In the first case, decoding the original data proves challenging for eavesdroppers. Even if they decode the RLNC-encoded data, in the second instance, the XOR packet embedding adds a layer of protection that necessitates the embedding key for successful decoding. However, it is crucial to consider additional security measures to protect highly sensitive data. Therefore, the goal is to apply RLNC on embedded XOR-encoded packets to enhance performance. We simplify our approach by breaking it down into distinct steps for clarity as shown in Fig. 2.

1. We start with a message consisting of N packets, for example, P1 to P6. We divide the packets into two generations: generation one (G1) consists of the initial n packets, and generation two (G2) consists of the remaining (N − n) packets. Using XOR network coding, we perform systematic XOR operations within each generation separately. This process creates two sets of XOR-encoded packets: one for G1 and another for G2 using a field size of GF(2).

2. This method supports transmitting n generations simultaneously for an even number of packets, but switches to a single generation for the last block of packets when the total count is odd. To simplify, we use n = 2.

3. To enhance security, we embed G1 and G2 into each other, resulting in a fresh methodically embedded packets (outer-code). The embedding follows this pattern: P1, P4, P1 ⊕ P2, P4 ⊕ P5, (P1 ⊕ P2) ⊕ P3, (P4 ⊕ P5) ⊕ P6.

4. Subsequently, we apply RLNC to the embedded outer code, using a field size of GF(2) with its two elements, 0 and 1. This simplifies computations and reduces complexity in the RLNC inner coding stage.

5. At the receiver, the decoder collects at least k coded packets and employs progressive Gaussian elimination for outer-code recovery.

6. As illustrated in Fig. 2, the outer-code is subsequently disentangled and decoded via a straightforward XOR operation. This procedure comprises two distinct stages:

∙ We extract all odd indexed packets from the decoding matrix and by performing a simple XOR operation, the first generation of packets P1 to P3 (i.e., G1) is recovered.

∙ Similarly, all the indexed even packets are extracted and decoded, recovering the second generation of packets P4 to P6 (i.e., G2).

7. Finally, we pass the packets to the application layer in the original order, i.e., from P1 to P6. Find the whole process described in Fig. 4

In XORE-NC, the data encryption key mechanism includes systematic XOR network coding, interweaving XOR-coded packets from two generations to form an embedded outer code, and applying RLNC. The receiver decodes this outer code, uses an unembedding key to recover systematic XOR-coded packets, and then decodes these to obtain the original packets. These combined layers effectively enhance data security by complicating unauthorized access and thwarting eavesdroppers.

In the following section, we present a mathematical model to support this approach.

Ⅳ XORE-NC: Mathematical Model

To create a mathematical model for the approach, we break down the process into key components and describe them mathematically. The approach involves message splitting into generations, XOR operations, and Random linear network coding operations.

4.1 System Parameters

We define some variables:

[TeX:] $$\varepsilon$$ : A range of erasure probabilities, [TeX:] $$\varepsilon \in$$ [0.1, 0.8]

G : Generation size.

[TeX:] $$\mathbb{P}$$ : Packet size in bits.

N : Number of packets.

M : Original message

f lag : Indicates whether the last message block is of size G (flag = 1) or 2G (flag = 0).

4.2 XORE-NC: Encoding Process

Consider a message M consisting of N packets, each with a size of P bits per packet.

Equation (1) denotes that M is a binary matrix with dimensions N ￗ P. Based on the generation size, G, for each block in M starting at index i

Subsequently, for each index j from 1 to G − 1:

The embedded outer coded packet, E , is constructed by interleaving G1 and G2:

Then, the flag type is set to zero, f lag = 0 since the number of packets in E [k] is a multiple of 2G.

4.2.1 Handling the Last Block

If the number of packets, N, is not a multiple of 2G, the last block will be of size G. In this situation, the embedded outer code, E , is constructed by just assigning the last message block to E given by equation (5). This is a unique scenario where there is no need for disentangling during the decoding process.

Where l is the last unpairable packet of the message block. Then, the flag is set to one, f lag = 1. Note that in this scenario, the embedded packet E[kl] lacks a pair. From equations (4 and 5), equations (6 gives a general expression for the embedded outer code.

4.2.2 Applying RLNC encoding over the embedded message

Random Linear Network Coding involves generating linear combinations of packets with coefficients chosen randomly from a finite field [TeX:] $$\mathbb{F}$$. Coefficients, denoted as C, are generated and the size of C depends on the generation size being encoded (i.e., 2G or G). The RLNC inner code, X, is then computed by performing matrix-vector multiplication using the coefficients C and the embedded outer code E :

Where R is either G or 2G. [TeX:] $$X_i$$ is the i-th encoded packet. [TeX:] $$C_{ij}$$ represents the coefficient of packet [TeX:] $$E_j$$ in encoded packet [TeX:] $$X_i$$. The summation limit extends up to 2G when [TeX:] $$E_j$$ is a multiple of 2G, and it extends up to G when [TeX:] $$E_j$$ is not a multiple of 2G.

4.3 XORE-NC: Decoding process

The encoded packet X obtained in equation (7) is passed to the RLNC decoder, which calculates the extended row-reduced echelon form ([TeX:] $$E x t_{\text {rre f}}$$) of the augmented matrix given by equation (8).

Based on equation (7), the embedded outer code, [TeX:] $$E_j$$, can be solved with equation (9) and extracted as presented by equation (10).

However, initially, the decoding process is carried out based on the flag type of the received RLNC inner code, X . To extract the outer code E j computed by equation (9) from the E xtrre f in equation (8), we use equation (10). The extraction starts from the G-th position for f lag = 1, and from the 2G-th position for flag = 0.

Where [TeX:] $$E X t_{\text {rre } f}$$ [2G :] denotes a subset of E xtrre f from index 2G to the end, and E xtrre f [G :] denotes a subset from index G to the end. We first consider the case for which flag = 0. Given an array E with n elements, where [TeX:] $$E=\left[\begin{array}{lllll} e_0, & e_1, & e_2, & \cdots ; & e_{n-1} \end{array}\right]$$, and n is even (i.e., 2G), you can distribute this array as:

Where [TeX:] $$L_1$$ and [TeX:] $$L_2$$ consists of elements at even indices and at odd indices respectively. Then, to reconstruct the unembedded coded packet, a concatenated list ([TeX:] $$L_C$$) is formed by concatenating [TeX:] $$L_1$$ and [TeX:] $$L_2$$ given by:

Summarily, the operation can be expressed as:

To reconstruct the original message (i.e., M), we initialize a matrix for decoded message y of size (2G,[TeX:] $$\mathbb{P}$$) with all elements initialized to zeros:

Matrix wise, equation (14) is expressed thus,

Set the first row of y to the values in the first row of unembadded packets, [TeX:] $$L_C$$ :

Set the G-th row of the decoded message, y to the values in the G-th row of [TeX:] $$L_C$$ :

For each i from 1 to G - 1:

Let [TeX:] $$Y_{2 G}=\left[\begin{array}{llll} y_1, & y_2, & y_3, & \cdots, y_N \end{array}\right]$$, where [TeX:] $$Y_i$$ represents the i-th decoded block, N is the total number of decoded blocks and N is a multiple of 2G. The complete decoded message, denoted as [TeX:] $$Y_{2G}$$, is obtained by concatenating all the decoded blocks [TeX:] $$Y_{2Gi}$$ as seen in equation (22).

In this expression, ∥represents the concatenation operation. The resulting decoded message ([TeX:] $$Y_{2G}$$), contains all the decoded information from the individual blocks and represents the final reconstructed message.

Secondly, consider the case for which flag = 1. In this case the generation of G packets has no pair and was sent unembedded. Hence, its decoding process is completed after the initial decoding process. Thus, from equation (10), [TeX:] $$E=\text{Ext}_{\text {rre f}}$$ [G :] and

As a result, in cases where the last block of message is not a multiple of 2G (i.e., the number of packets, N, is odd), the decoded packet, denoted as [TeX:] $$Y_G$$, can be explicitly represented by equation (24).

The complete decoded message Y for this scenario can be expressed as the concatenation of [TeX:] $$Y_{2G}$$ and [TeX:] $$Y_G$$ as defined in equation (25);

Otherwise, if the number of packets N is a multiple of 2G, then Y is given by

4.4 Data confidentiality optimization

Data confidentiality is vital in modern communication systems, particularly when safeguarding sensitive information from eavesdroppers is crucial. XORE-NC offers strategies and techniques to enhance data confidentiality in network coding, supported by relevant mathematical expressions.

4.4.1 Embedding Key Mechanism

To enhance data confidentiality in XORE-NC, we employ an embedding key mechanism, adding an extra layer of protection to the encoded data, making it harder for unauthorized access. This key is integrated during XOR-embedded packet generation, creating complex interdependencies among packets as in equations (4), (5), and (6). For example, when XORing packets P1 and P2, it involves additional XOR operations with P3 and P4. Decoding this data requires not only retrieving XOR-encoded packets but also possessing the embedding key to navigate these intricate dependencies. This embedding key significantly heightens the challenge for eavesdroppers in deciphering the original data. Even if they decode the RLNC-encoded data, this approach adds security by obscuring packet relationships and requiring knowledge of the embedding key for successful decoding.

4.4.2 Use of Random Linear Network Coding (RLNC)

In addition to the embedding key mechanism, XORE-NC utilizes RLNC to enhance data confidentiality. RLNC adds a layer of complexity by creating linear combinations of packets using coefficients selected randomly from a finite field (as illustrated in equations 7 and 9). These coefficients, denoted as Ci j , are applied during the encoding process to the XOR-embedded packets, as shown in equation 7. By introducing randomness and complexity, these coefficients make it even more challenging for eavesdroppers to reverse-engineer the original content. Consequently, data confidentiality is improved by increasing the difficulty of unauthorized decryption.

Ⅴ. Performance Evaluation

In network communication systems, optimizing data transfer is critical. XORE-NC transmits twice as many packets as RLNC for generation sizes [TeX:] $$G \in 5$$, 10 and packet sizes [TeX:] $$\mathbb{P} \in$$ 1B, 2B, suggesting a potential for increased throughput.

In Fig. 5 with G = 5, while RLNC may seemto require less added transmission for 1-byte packets than XORE-NC, the latter compensates by transmitting twice the number of generations, effectively doubling the secured data per transmission. This increased data protection does not proportionately raise the added transmission, affirming XORE-NC efficiency. When G is increased to 10, although the efficiency gains for 1-byte and 2-byte packets are comparable for both schemes, XORE-NC dual-generation transmission provides enhanced confidentiality without significantly impacting overhead, especially at higher erasure probabilities - the likelihood that a transmitted packet will be lost and not received by the destination. This balance of security and efficiency positions XORE-NC as a superior choice for secure, high-throughput communications under variable network conditions

As depicted in Fig. 6, XORE-NC exhibits the lowest encoding delay for 1-byte packets across all erasure probabilities when G = 5, underscoring its superior efficiency, which encompasses not only speed but also the heightened data confidentiality integral to its design. Despite transmitting secured data that requires more complex encoding operations, XORE-NC maintains a lower delay than RLNC for both 1-byte and 2-byte packets. When the generationsize increases to G = 10, we observe an expected rise in encoding delay for both schemes due to larger data volumes and the additional security computations. Nevertheless, XORE-NC continues to demonstrate the quickest encoding times, especially for smaller packets. This trend suggests that XORE-NC’s approach to data confidentiality, while introducing additional processing steps, still allows it to outperform RLNC in terms of encoding speed, making it highly suitable for scenarios demanding both swift and secure data transmission.

Fig. 7 shows overall latency, crucial from encoding to decoding, under various scenarios. For G=5, the latency trends upward steadily with the rise in erasure probability. Notably, XOR-NC shows commendable efficiency, as it does not proportionally increase latency despite transmitting twice as many packets compared to RLNC with the same byte size. This suggests that the efficient encoding utilized by XOR-NC does not significantly burden transmission time. Moving to G = 10, latency rises for both schemes, but XOR-NC and RLNC show comparable latency, regardless of payload size. Despite larger payloads increasing latency, the graph shows XOR-NC and RLNC have similar latency rises, indicating no significant advantage for XOR-NC encoding over RLNC in this case. However, Fig. 8 reveals XOR-NC capacity to handle larger data volumes and more challenging erasure conditions effectively, underscoring its potential for secure, high-throughput environments. The data thus underscores XOR-NC as a suitable candidate for scenarios demanding robust security without compromising on transmission efficiency. XORE-NC’s latency performance may decrease with fewer packets, e.g., from 60 to 20, indicating its suitability for high data rate scenarios.

Fig. 9 shows that the decoding delay for both XORENC and RLNC increases with erasure probability for 1 and 2-byte packets and generation sizes of 5 and 10. The sharper rise in XORE-NC decoding delay, particularly for larger packets, might be attributed to the more complex data unscrambling necessitated by its enhanced confidentiality features. Although XORE-NC encoding and transmission are efficient, the intricacies of its secure encoding impact decoding performance under higher loss conditions. Future enhancements, such as integrating a sliding window protocol, could potentially mitigate this by streamlining the decoding process, even in scenarios with high erasure probabilities, thus further optimizing XORE-NC robustness.

Ⅵ. Conclusions

Based on the presented findings, XOR-Embedded Network Coding (XORE-NC) offers a promising approach to enhance data confidentiality in network coding. By employing an embedding key mechanism and Random Linear Network Coding (RLNC), it adds layers of protection, making unauthorized access and decryption more challenging. XORE-NC demonstrates improved reliability, reduced encoding delay, and lower latency and throughput compared to traditional RLNC. However, it requires further research to address higher decoding delay. In conclusion, XORE-NC presents a robust solution to bolster data confidentiality in communication systems while maintaining efficient data transmission.