{'fraction_non_alphanumeric': 0.03478732470752305, 'fraction_numerical': 0.0076702564499883785, 'mean_word_length': 4.524288465653756, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Impact of Partial Packet Recovery on the Inherent Secrecy of Random Linear Coding

This paper considers a source, which employs random linear coding (RLC) to encode a message, a legitimate destination, which can recover the message if it gathers a sufficient number of coded packets, and an eavesdropper. The probability of the eavesdropper accumulating enough coded packets to recover the message, known as the intercept probability, has been studied in the literature. In our work, the eavesdropper does not abandon its efforts to obtain the source message if RLC decoding has been unsuccessful; instead, it employs partial packet recovery (PPR) offline in an effort to repair erroneously received coded packets before it attempts RLC decoding again. Results show that PPR-assisted RLC decoding marginally increases the intercept probability, compared to RLC decoding, when the channel conditions are good. However, as the channel conditions deteriorate, PPR-assisted RLC decoding significantly improves the chances of the eavesdropper recovering the source message, even if the eavesdropper experiences similar or worse channel conditions than the destination.


I. INTRODUCTION
Random linear coding (RLC), which encompasses fountain coding and network coding, generates coded packets that are random linear combinations of input data packets. RLC has the potential to increase throughput and improve robustness [1] but has also been considered for information-theoretic secure communications because eavesdroppers cannot necessarily retrieve source data from a subset of received coded packets. Ning and Yeung [2] first formulated the concept of secure network coding, while Adeli and Liu [3] studied probabilistic weak security for linear network coding. Niu et al. [4] computed the intercept probability of RLC for wireless broadcast applications, that is, the probability that an eavesdropper will accumulate the required number of coded packets for the reconstruction of the source data. The analysis in [4] was later revisited and refined by Khan et al. [5]. Since then, the intercept probability has been analyzed in different settings; for example, layered RLC was studied in [6], sparse RLC was investigated in [7] and applications of secure RLC-encoded data transfer were explored in [8], [9].
RLC decoding at a legitimate destination or an eavesdropper discards received coded packets that have been corrupted by errors and attempts to reconstruct the source packets from correctly received coded packets. In this paper, we assume that an eavesdropper does not discard corrupted coded packets but stores them and utilizes them offline, i.e., at a later instance, if RLC decoding has been unsuccessful. Partial packet recovery (PPR), proposed in [10], is employed to repair stored packets in polynomial time and improve the chances of the eavesdropper recovering the source packets. The motivation for this paper is to investigate RLC decoding combined with PPR from the perspective of an eavesdropper, study the impact of PPRassisted RLC decoding on the intercept probability, contrast it with conventional RLC decoding and observe tradeoffs between secrecy and reliability.
The remainder of this paper has been organized as follows: Section II presents the system model, including definitions and notation. Section III proposes full-rank nonsystematic RLC encoding at the source, while Section IV studies PPR-assisted RLC decoding at an eavesdropper and briefly describes two methods for repairing corrupted packets. The chances that a legitimate destination or an eavesdropper will recover the source message are discussed in Section V. Results, which give insights into secrecy-reliability tradeoffs, are presented in Section VI and key findings are summarized in Section VII.

II. SYSTEM MODEL
We consider a network setup whereby a source S transmits a message to a legitimate destination D in the presence of an eavesdropper E, as depicted in Fig. 1. Before initiating transmission, the source segments the message into packets. Each source packet has been modeled as a sequence of symbols from a finite field of elements, denoted by F , where is a prime power. The source packets of length can be expressed as a matrix U ∈ F × , where F × denotes the set of all × matrices over F . RLC [11] is used to encode the source packets into ≥ coded packets, each of length symbols. The coded packets can also be expressed in matrix form as X ∈ F × . The relationship between matrices X and U is: where G ∈ F × is known as the generator matrix. Typically, the entries of G are chosen uniformly at random from F . As explained in [10], a seed can be used to initialize the pseudorandom number generator that outputs the entries of G. Given that the value of the seed can be conveyed in the headers of the coded packets, we assume that both the destination and the eavesdropper have knowledge of G. Note that the eavesdropper could be a legitimate destination in a different occasion - hence, it is equipped with the same pseudo-random number generator -but is not authorized to receive the private source message in this occasion. The link connecting the source to the destination has been modeled as a memoryless channel characterized by packet error probability D or, equivalently, by bit error probability 1 − (1 − D ) 1/ . Similarly, the link connecting the source to the eavesdropper is characterized by packet error probability E . We assume that the eavesdropper experiences, on average, similar or worse channel conditions than the destination, that is, E ≥ D . Let D be the number of coded packets that have been successfully received by the destination, and D be the ordered set of the row indices of X that correspond to correctly received coded packets, i.e., |D | = D ≤ . The destination constructs matrix X D from the D correctly received coded packets and matrix G D from D rows of G with indices in D. The source message, represented by matrix U, can be obtained from X D = G D U if the rank of G D is . In that case, the relationship X D = G D U can be seen as a system of D ≥ linear equations, which can be reduced to a system of linearly independent equations with unknowns, i.e., source packets. This × system can be solved, e.g., using Gaussian elimination, and return a unique solution for U. Similarly, the overhearing eavesdropper collects E coded packets, builds the ordered set E of row indices, constructs matrices X E and G E , and attempts to obtain U from X E = G E U.
Khan et al. considered this system in [5] and derived closedform expressions for the probability that the eavesdropper will gather enough coded packets to recover the source message. The authors also quantified the gain in secrecy when the source broadcasts up to max coded packets but ceases transmission as soon as the destination sends a notification over a perfect feedback channel confirming receipt of the source message. In this paper, the eavesdropper attempts to decode the E correctly received coded packets concurrently with the legitimate destination, as in [5], but does not discard the − E erroneously received coded packets. Instead, the eavesdropper employs PPR [10] offline in an effort to repair received coded packets that have been corrupted by errors and improve the chances of the RLC decoder recovering the source message. Section III discusses RLC encoding at the source, while Section IV adapts the PPR process presented in [10] to the system model under consideration and describes PPRassisted RLC decoding at the eavesdropper.

III. RLC ENCODING AT THE SOURCE
RLC encoding is typically non-systematic, that is, the source packets are encoded into packets, which are random linear combinations of the source packets, as described in Section II. The probability that the legitimate destination will successfully recover the source packets from D ≤ received coded packets is given by [12]: RLC encoding can also be systematic, in which case the first of the transmitted packets are identical to the source packets while the remaining − packets are random linear combinations of the source packets. In systematic RLC, the generator matrix G can be expressed in standard form: where I is the × identity matrix and P is a ( − ) × randomly-generated matrix with entries from F . The probability of the destination recovering the source packets, upon receipt of D ≤ error-free packets, can be calculated from: where ℎ lim = max (0, D + − ) [13].
In systematic RLC, the eavesdropper could receive some of the source packets and could thus gain direct access to parts of the source message even before it attempts to decode the collected packets. Non-systematic RLC offers the advantage of inherent secrecy but exhibits a lower probability of message recovery at the destination than systematic RLC, as proven in [13]. For example, let us assume that the destination successfully received the first transmitted packets. If systematic RLC has been used, the destination will recover the source message. If non-systematic RLC has been employed, recovery of the source message is not guaranteed, as the first transmitted packets may not be linearly independent. In that case, the destination will need more than packet transmissions at the risk of allowing the eavesdropper to collect more packets and possibly recover the source message.
In order to combine the inherent secrecy of non-systematic RLC with the reliability of systematic RLC, we could use nonsystematic RLC constructions defined by a generator matrix of the form: To obtain G, the seed of the pseudo-random number generator should be chosen to ensure that the top randomly-generated rows of G are linearly independent, that is, rank(G ) = .
Column-wise Gaussian elimination can transform G into standard form and convert the proposed full-rank non-systematic RLC into an equivalent systematic RLC, i.e., Full-rank non-systematic RLC retains the inherent secrecy features of non-systematic RLC, while its equivalence to systematic RLC suggests that (4) provides the probability of the destination recovering the source packets when D ≤ coded packets have been received without errors. Expression (6) will be used in the following section, which looks into how the eavesdropper attempts to retrieve the source message.

IV. EAVESDROPPING ENHANCED BY PPR
We explained in Section II that E is the ordered set of E row indices of X that correspond to error-free coded packets received by the eavesdropper. The indices of the remaining − E rows of X, which identify erroneously received coded packets stored at the eavesdropper, form E = {1, . . . , }\E.
Based on E, the eavesdropper constructs X E and G E , and uses RLC decoding to solve X E = G E U for U and recover the source message. If rank(G E ) = , the source message can be recovered. If rank(G E ) < , the eavesdropper turns to set E, and utilizes sparse recovery principles to repair erroneously received coded packets and complement RLC decoding.
More specifically, let Y be an erroneous copy of X that has been received by the eavesdropper, defined as: The error matrix E contains non-zero elements in positions where errors have occurred and zero elements in the remaining positions. Note that the eavesdropper has knowledge of Y and G only. The × ( − ) parity-check matrix H can be derived from the × generator matrix G, as follows: so that: Matrix P can be obtained from (6). Matrix negation in (8) is performed in F , e.g., −P = P in F 2 . Multiplication of Y by H produces the ( − ) × syndrome matrix S, i.e., S = H Y. Using (9), we find that the relationship between the syndrome matrix S and the error matrix E is: Given that our focus is on the − E erroneously received coded packets, we use the set E to isolate the − E of the rows of Y, X, E and H, and construct Y E , X E , E E and H E . As a result, expressions (7) and (10) change to: and respectively. If the -th column of S and E E is denoted by [S] * , and [E E ] * , , expression (12) can be re-written as independent systems of − linear equations with − E unknowns per equation: Mohammadi et al. [10] observed that erroneously received coded packets usually contain large error-free segments, thus E E is a sparse matrix, that is, E E has more zero entries than non-zero entries. Based on this observation, the solution to (13) can be formulated as an 'ℓ 0 minimization' problem: where w ∈ F − E is a row vector that should satisfy constraint (14b) and have the minimum possible number of non-zero entries. To count the non-zero entries in w, the ℓ 0 norm is used, which is defined as w 0 = | 1 | 0 + . . . + | − E | 0 assuming that 0 0 = 0 [14]. Two PPR methods for the evaluation ofÊ E were proposed in [10]. The first approach, which is inspired by the compressed sensing (CS) literature, replaces the non-convex ℓ 0 norm in (14a) with the convex ℓ 1 norm, solves the optimization problem over the set of real numbers, and rounds off the derived values to the nearest elements of F . The second approach, referred to as syndrome decoding, considers (14) and initiates an exhaustive search for a candidate solution; the sparsity of the row vector w is gradually reduced, i.e., the number of non-zero entries in w increases, and the search concludes when the sparsest vector w that satisfies constraint (14b) has been identified.
When candidate solutions for the columns ofÊ E have been obtained andÊ E has been evaluated, an estimate of X E , denoted byX E , can be derived using (11): MatrixX E is the outcome of the eavesdropper's attempt to repair the received matrix Y E . Let denote the number of rows inX E that correspond to successfully repaired coded packets, e.g., packets that passed Cyclic Redundancy Check (CRC) verification. The indices of the repaired coded packets are removed from set E and added to set E, and the corresponding rows ofX E are moved to X E . The cardinalities of sets E and E change to − E − and E + , respectively, while the dimensions ofX E and X E change to ( − E − ) × and ( E + ) × , respectively. The indices of the repaired coded packets are also used to identify the rows of the generator matrix G that should be inserted in G E . If PPR increases the rank of the enlarged ( E + ) × matrix G E to , the RLC decoder at the eavesdropper will recover the source message. The computational complexity that PPR adds to RLC decoding for operations in F 2 has been discussed in [10]. Essentially, PPR allows the eavesdropper to improve the chances of repairing and decoding the collected coded packets at the cost of increased complexity. This fact makes PPR suitable for offline use. The probability that the eavesdropper will recover the source message, referred to as the intercept probability [5], when RLC decoding is used, and the challenges in computing the intercept probability when PPR-assisted RLC decoding is employed, are discussed in the following section.

V. DECODING AND INTERCEPT PROBABILITIES
We initially investigated the inherent secrecy of RLC in [5] and obtained a closed-form expression for the intercept probability when both the destination and the eavesdropper employ RLC decoding. This expression will serve as a benchmark for the intercept probability when the eavesdropper uses PPRassisted RLC decoding. For this reason, and for the sake of completeness, we summarize below the analysis in [5].

A. RLC Decoding
Recall that the source broadcasts ≥ coded packets, where is constrained by an upper limit max . The destination and the eavesdropper receive D ≤ and E ≤ error-free coded packets, respectively. Let denote a receiver, either the destination D or the eavesdropper E, that is, ∈ {D, E}. Also, let be a random variable, which represents the number of transmitted coded packets that are required for to recover the source packets. The Cumulative Distribution Function (CDF) of , which describes the probability that the receiver will recover the source packets after coded packets have been transmitted, for ≤ ≤ max , takes the form: Note that s ( , , ) has been used in place of ns ( , ) in (16) because typical non-systematic RLC, which was considered in [5], has been replaced by full-rank non-systematic RLC, which was defined in Section III. Based on the definition of ( ), the probability that the destination D will recover the source message by the time max coded packets have been transmitted or sooner, is given by and is commonly referred to as the decoding probability. The Probability Mass Function (PMF) of , which is the probability that the receiver will recover the source packets only after the -th coded packet has been transmitted, but not sooner, can be obtained from the CDF as follows: The intercept probability can be expressed as the sum of the following two terms: where E (·) and D (·) can be obtained from (16) for = E and = D, respectively, and D (·) can be obtained from (18) for = D. The first term in (19) denotes the probability that the destination will recover the source message after the -th coded packet has been transmitted, for ≤ ≤ max , and the eavesdropper will recover it sooner or concurrently with the destination. The second term in (19) represents the probability that only the eavesdropper will be successful in recovering the source message when the maximum number of coded packet transmissions, max , is reached.
Expression (19) assumes that the sequence of coded packets delivered over the source-to-destination link is independent of the sequence delivered over the source-to-eavesdropper link. In practice, the interdependence of the two sequences becomes weaker as the value of the product D or E increases [15] and, hence, the accuracy of expression (19) improves.

B. PPR-assisted RLC Decoding at the Eavesdropper
Whereas the rank of G E is important in RLC decoding at the eavesdropper, the spark of the transpose of H E plays a key role in PPR-assisted RLC decoding. The term 'spark' of a matrix was first coined by Donoho and Elad in [16] and is defined as follows for the case of H E : Definition 1 ([17], p.23). The spark of H E is the smallest number of columns from H E that are linearly dependent. Using mathematical notation, we can write: If we consider the systems of equations defined in (13) and focus on the solution to the -th system described in (14), the spark of H E gives the following criterion for the uniqueness of sparse solutions: Theorem 1 ([17], p.24). If a system of equations, as in (14b), has a solution w obeying: then this solution is necessarily the sparsest possible.
Computation of the intercept probability for an eavesdropper employing online RLC decoding and offline PPR-assisted RLC decoding requires the inclusion of additional terms in (19). These terms should account for the probability that the RLC decoder at the eavesdropper will fail to recover the source message at first, but will succeed if PPR repairs a sufficient number of erroneously received coded packets. More specifically, a correctly estimated column of E E : (a) either satisfies (14b) and obeys (20), i.e., the estimated column is the sparsest possible solution, (b) or satisfies (14b) without obeying (20). PPR-assisted RLC decoding will recover the source packets: all of the erroneously received coded packets and reconstructing the full-rank generator matrix G, or • if PPR correctly estimates some of the columns of E E , because of a combination of (a) and (b), and repairs some of the erroneous coded packets, leading to an increase in the rank of G E to , as described in Section IV. Derivation of the probability of fully or partially reconstructing matrix E E and subsequently obtaining an increased-size full-rank matrix G E , where G E and E E are random matrices over F , is a non-trivial problem and a closed-form expression is not available in the literature, to the best of our knowledge. For this reason, we use the analysis in Section V-A to develop and validate the simulation results of the system in Fig. 1, when the eavesdropper employs RLC decoding only. Then, we equip the eavesdropper with PPR capabilities and carry out simulations to measure the impact of PPR on the intercept probability, as we explain in the following section.

VI. RESULTS AND DISCUSSION
In order to investigate the inherent secrecy of RLC, we consider a source employing full-rank non-systematic RLC over F 2 to encode a message that has been segmented into = 20 packets, each consisting of = 128 bits. The intercept probability int has been measured for different values of packet error probabilities D and E , when the destination employs RLC decoding and the eavesdropper also relies on RLC decoding or combines PPR with RLC decoding. Of the two PPR methods summarized in Section IV, we implemented syndrome decoding (SD). The CS-based method can recover the source message with a slightly higher probability than SD for a broad range of channel conditions but at a significantly higher computational cost [10]. Given that the information value of the source message may decline with time, we opted for the less time-consuming SD method to complement RLC decoding. We refer to this joint scheme as 'RLC with SD'.
We first study the case where the source broadcasts coded packets until the destination recovers the source message, that is, the number of transmitted coded packets is not constrained by an upper limit max . This is equivalent to setting max → ∞ in order to achieve dec = 1. The intercept probability has been plotted against D in Fig. 2, where D varies from 0.01 to 0.1 and E takes values in {0.1, 0.15, 0.2}. For a fixed value of E , we observe that as the value of D increases and the source is compelled to broadcast more coded packets to ensure that the destination will recover the source message, the chances of the eavesdropper also reconstructing the source message increase. Note that expression (19), which has been adapted for full-rank non-systematic RLC encoding proposed in Section III, generates theoretical predictions for the intercept probability that closely match simulation results when the eavesdropper employs RLC decoding. Fig. 2 shows that if SD is used offline to complement RLC decoding, a gain in the intercept probability will be attained, which increases with D and, in particular, with E .
Let us now consider the case where the source sets a limit max on the number of transmitted coded packets, so that the decoding probability at the destination is at least 0.99, that is, dec ( max ) ≥ 0.99 but dec ( max − 1) < 0.99. Expression (17) was used to determine max for different values of D , and their relationship has been plotted in Fig. 3 (bottom). The intercept probability for increasing values of D and max is shown in Fig. 3 (top), where E = D + for ∈ {0, 0.05, 0.1}. We observe that, as channel conditions deteriorate, the inherent secrecy of RLC is not severely compromised when the eavesdropper relies on RLC decoding to obtain the source message; for E > D , the intercept probability increases marginally but then plateaus and reduces slowly, as D shifts from 0 to 0.5. However, when the eavesdropper combines RLC with SD, the intercept probability increases noticeably and approaches 1 for large values of D . This result establishes that a poor sourceto-destination channel, which could have been intentionally degraded by an eavesdropper who generates artificial noise, greatly improves the decoding capability of the eavesdropper when RLC with SD is used, even if the eavesdropper experiences similar or worse channel conditions than the destination.
Given that a scenario where E = D for D → 0 is not likely to occur, limiting the value of the intercept probability for all other cases is of importance for systems that rely on information theoretic security. Instead of raising the value of max as D increases in order to maintain a fixed decoding probability at the destination, as in Fig. 3, we fix the value of max in Fig. 4 and trade reliability for secrecy. We observe that a decrease in the value of max suppresses information leakage and reduces the intercept probability, when the eavesdropper combines SD with RLC decoding, but inevitably lowers the decoding probability. The value of max also determines the range of D values over which the system could operate. For example, if max = 25, the destination will achieve dec = 0.8 for D = 0.1 while the worst-case intercept probability ( E = D ) will be limited to int = 0.57. However, the system may be required to support the same decoding probability ( dec = 0.8) for D = 0.2; Fig. 4 indicates that max will have to increase from 25 to 29 as long as the subsequent increase in the worstcase intercept probability ( int = 0.7) is tolerable, e.g., because additional security measures have been implemented or the source message does not carry sensitive information.

VII. CONCLUSIONS
This paper investigated the impact of partial packet recovery on the inherent secrecy of random linear coding. Results demonstrated that syndrome decoding combined with random linear decoding can boost the probability of an eavesdropper recovering a message transmitted from a source to a legitimate destination. Of particular interest was the observation that this probability increases as the channel conditions between the source and the destination, but also between the source and the eavesdropper, deteriorate. The eavesdropper has thus an incentive to introduce artificial noise and actively impair data packets transmitted by the source. If information theoretic security is essential, system requirements should dictate a limit on the number of packet transmissions and a threshold on the channel conditions, beyond which transmission should cease in order to keep low the probability of the eavesdropper reconstructing the source message.