WO2011044919A1

WO2011044919A1 - Method for network coding transmission

Info

Publication number: WO2011044919A1
Application number: PCT/EP2009/007390
Authority: WO
Inventors: Alban Hessler; Dirk Westhoff
Original assignee: NEC Europe Ltd
Current assignee: NEC Europe Ltd
Priority date: 2009-10-14
Filing date: 2009-10-14
Publication date: 2011-04-21
Anticipated expiration: 2012-04-14

Abstract

A method for network coding transmission from a sending node (S) to at least one receiving node (R1, R2), possibly via one or more forwarding nodes (F1, F2), wherein the transmission data is divided into single plaintext packets p_i, wherein payloads X are generated from said plaintext packets p_i, by means of encoding, and wherein each of the packets being transmitted is composed of one of said payloads X, and a coefficient vector C that carries the information on which of said plaintext packets p_i, contributed to the encoding, is characterized in that, before transmitting a packet, said coefficient vector C is solely being encrypted.

Description

METHOD FOR NETWORK CODING TRANSMISSION

The present invention relates to a method for network coding transmission from a sending node to at least one receiving node, possibly via one or more forwarding nodes, wherein the transmission data is divided into single plaintext packets Pi, wherein payloads X are generated from said plaintext packets p, by means of encoding, and wherein each of the packets being transmitted is composed of one of said payloads X, and a coefficient vector C that carries the information on which of said plaintext packets Pi contributed to the encoding.

In network coding transmission, an intermediary node can combine different packets together in order to diminish the number of transmissions, and thus increase the overall throughput of the network. To disseminate bulks of data over an unreliable medium to numerous receivers, rateless erasure codes, also known as fountain codes, are an efficient way to cope with various packet losses and reduce the need of backward channel. In such networks, a packet is composed of a payload X which carries network encoded data, and metadata C, the coefficient vector, sometimes also named "encoding vector", that carries the information on which plaintext packets p„ p_n representing the data stream contributed to the encoding.

In the context of the present invention the case is considered where the encoded packets are combinations of several (or, more precisely, one or more) source packets, and the metadata are bit-vectors of size π-bit describing which concrete plaintext packets p, have been considered in the encoded packets Xs. The receiver can decode the received encoded packets by solving a linear equation system. If packets get lost, it is not required at the sender side to resubmit the missing packet, say X_t. Instead, due to the "fountain" characteristic of the code applied at the sender side, just another random linear combination X_t+k can be transmitted.

In a multi-hop propagation scenario, a forwarding node may not only want to forward received encoded packets ,||C, but also generate freshly encoded packets by combining a subset of the already received encoded packets, e.g. X_f\\C_f = X_t xor X_k\\C_j + C_k . In general, therefore the node is required to compute X₍ = θ'₌, Χ, and C_f = ®'_i=1C_; . The coefficient vector C describes how the different plaintext packets were combined. Thus, the receiving node (as well as every intermediate node) knows what source plaintext packets p, contributed to the received encoded packet. For example assuming that the data stream is subdivided into packets p„ p₆ and in case the C, equals the bit string 000101 , the encoded packet X, has been generated by contributions of the plaintext packets p, Θ p₃.

The introduced network coding paradigm has recently been applied to various P2P (Peer-to-Peer) data streaming and WSN (Wireless Sensor Network) code image update scenarios to name only a few. Obviously, once deployed there is a growing need to enrich such concepts with security means. Solutions regarding the integrity and authenticity of incoming encoded packets have already been proposed, for instance in J.M. Bohle et al. "Security Enhanced Multi-Hop over the Air Re-Programming with Fountain Codes", SenseApp, 2009, 4th IEEE International Workshop on Practical Issues in Building Sensor Network Applications.

Currently, there is no work which explicitly deals with the confidentiality of encoded data. This may have two reasons: one camp argues that the encoding in itself is already a weak mean of encryption and therefore additional protection is not required anymore. Examples following this direction assume that the attacker can eavesdrop only on a subset of all transmission paths between source and destination(s). The other camp argues that there is no research challenge in weaving confidentiality into the network coding paradigm. According to this viewpoint, confidentiality is achieved by applying an encryption transformation E, either on the plaintext data or on the encoded data. This camp further argues to transmit either E(Xj,C) or E{X ,C or to apply the encryption on the plaintexts yet E(p,) before generating the X,. All these approaches have their drawbacks either with respect to security, CPU investment or with respect to the flexibility for generating new encoded packets on its way to the final multicast destinations. It is therefore an object of the present invention to improve and further develop a method for network coding transmission of the initially described type in such a way that, by employing mechanisms that are readily to implement, the confidentiality of the data is protected while computational and transmission overhead is minimized.

In accordance with the invention, the aforementioned object is accomplished by a method comprising the features of claim 1 . According to this claim such a method is characterized in that, before transmitting a packet, said coefficient vector C is solely being encrypted.

According to the invention it has been recognized that the drawbacks of state of art solution can be avoided by encrypting the coefficient vector instead of the encoded packet such that X, E(C). Although the encoded payload X, which was generated by applying fountain codes, is not directly encrypted, the fact that the coefficient vector C is encrypted provides some form of confidentiality also for the payload X. (As X is a random combination of d plaintext packets, it does neither provide any information about the concrete d nor does it reveal the chosen plaintext packets denoted as p„ .... p_d). Since the C, are encrypted, an attacker cannot modify encoded packets at will anymore (only randomly). Compared to state of the art approaches, the attacker cannot even know which packets he is combining. This can prevent the attacker from making attacks on the decoding process (i.e. increase the complexity of the decoding). Finally, it is to be noted that encrypting/decrypting a small coefficient vector \C\ is less CPU consuming than encrypting an in general much larger encoded packet | | for the data stream.

To demonstrate the benefits of the method in accordance with the present invention, it is to be recalled that decoding in conventional prior art approaches works by solving the linear equation system X = CP . C is a m x n matrix of linear independent coefficient vectors C with the property that rank(C)=n, X is the matrix of the m received encoded packets X_u..., X_m, and P is the desired matrix of cleartext packets with the i^,h row of P corresponding to packet p With the encryption approach of the present invention an attacker has no information about the matrix C as it is encrypted, thereby trying to infer P out of X with no additional information.

As concerns possible fields of applications, the method according to the present invention may be employed, e.g., in P2P applications where large data streams have to be transmitted in a distributed manner. Furthermore, due to its lightweight characteristic, it can suitably work on restricted embedded devices such as sensor nodes. Thus, a possible application scenario would be, for instance, "over the air" (OTA) reprogramming in wireless sensor networks (WSN). Generally, with the proposed invention, network coding can be applied in very hostile environment, for example, to thwart eavesdropping in wireless peer-to-peer networks.

According to a preferred embodiment the encryption scheme employed for encrypting coefficient vector C is an homomorphic encryption transformation, in particular an additively homomorphic encryption transformation. In such case it holds that E(a ® b) = E(a) ® E(b) for any plaintext pair a and b, a properly chosen additive operation <E> on the ciphertext, and another additive operation θ οη the plaintext. This approach has many benefits regarding network coding flexibility and performance. For instance, although the payload is concealed, still meaningful and syntactically network coding on two (or more) encoded and encrypted packets X„E(C,) and X_k, E(C_k) can be performed: X_f , E(C_f ) = X, ® X_k , E{C, ) ® E(C_k ) ; the operation Θ is the concrete encoding operation. Consequently, using this privacy homomorphism based encryption approach, an intermediate (forwarder) node can still apply network coding on the packets it forwards, but has no indication of what it is actually transmitting. An intermediate node performing network coding can combine any number of encoded packets.

In a conventional setting with E(X,C) such an in-network coding approach on encrypted data would only be possible if E() is homomorphic in respect to the operation θ , i.e. would result in the network coding operation in the plaintext field. So far "Θ "denotes the network coding operation on the cleartext and "® " on the ciphertext. With respect to low computational complexity it may be provided that the concrete encoding operation <8> is an exclusive OR (XOR) operation which would be the easiest case and which is actually an addition on Galois Field vectors of length n F_j . Due to this, when merging two or more encoded packets as described above, the resulting encoded packet always contains either one or zero plaintext contribution per plaintext but definitely not more. However, other operations may also be possible.

In a content distribution scenario, one or more sources or sending nodes distribute content to one or more recipients or receiving nodes. Furthermore, it is assumed that there are nodes on the path that can forward the data, without having any interest in the content. In such scenario it is advantageous that the sources and the recipients share cryptographic material, such that the recipients can decode privacy homomorphic encrypted data from the sources. For instance, it may be provided that a homomorphic encryption scheme is being applied which is symmetric and uses pairwise keys. This would be particularly beneficial with respect to the proposed encryption scheme retaining its "lightweight" advantages. However, without loss of generality, the proposed concept also works with other homomorphic encryption schemes, e.g. symmetric and groupwise keys but also asymmetric homomorphic schemes.

For instance, a symmetric scheme with group-wise keying that may be applied is the one from Domingo-Ferrer. This scheme is described in detail in J. Domingo- Ferrer, A Provably Secure Additive and Multiplicative Privacy Homomorphism, Proc. Fifth Information Security Conf. (ISC'02), pp. 471 -483, 2002, the entire disclosure of which is incorporated herein by reference. As a symmetric one with pairwise keys the homomorphic encryption scheme having been proposed by Castelluccia, Mykletun and Tsudik (as described in C. Castelluccia et al., Efficient Aggregation of Encrypted Data in Wireless Sensor Networks, Proc. Second Ann. Int'l Conf. Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous), July 2005, the disclosure of which is also incorporated herein by reference). Finally, as a candidate for an asymmetric additively homomorphic scheme the EC-Elgamal scheme may be applied (as described in T. EIGamal, A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, Proc. Ann. Int'l Cryptology Conf. (CRYPTO'85), vol. IT-31 , no. 4, pp. 469-472, July 1985, the disclosure of which is also incorporated herein by reference.

Since the proposed encryption approach is lightweight it has some potential weaknesses. An attacker has some means to break the system independently of the concrete strength of the chosen underlying homomorphic encryption transformation. To optimize the strength it may be provided that the concrete value of the degree d (the number of plaintext packets that are used to generate an encoded packet) is chosen to be greater than a configurable threshold. Furthermore, it proves to be beneficial if the plaintext contains only little or no structural information that might help an attacker to decode transmitted packets. In addition, the amount of plaintext packets |p| , n, into which the plaintext data stream is subdivided, i.e. the size of said coefficient vector C, should be sufficiently high.

Generally, it holds that the size of the payload is much larger than the size of the coefficient vector (|X| » |C| ). The size |C| reflects the number of plaintext packets in which the whole data stream is subdivided whereas the size| | is basically limited by the MTU (Maximum Transmission Unit) of the network or other parameters describing the packet size. (e.g. Ethernet 1500 byte, e.g. 1480 byte IPv4 data). One can also think about settings, e.g. in WSNs with IEEE 802.15.4 and a huge data stream to be transmitted; here, since | | < 40 bytes, it can be that the ratio |^|/|C| is not large anymore. Consequently, as already outlined above, regarding the performance (time for encryption and for decryption) it is recommendable to encrypt the C and not the X. However, with respect to the security level, one should make sure that the transmission data is divided into a minimum amount of packets, |C| > 128 bit, corresponding to an acceptable key size for symmetric keys. Regarding a lightweight and balanced overall security level the C may be padded to 64-bits in case it represents a data stream which does not require such a number of bits.

To improve the security level, and in particular to thwart statistical analysis of the data transmitted, which could lead to the revealing of the plaintext, it may be provided that the degree distribution Ω for the encoding is chosen to have a minimum degree d_min≥ T_drop that is significantly higher than one, e.g. T_drop = 3 or T_drop = ⁴· Although such a choice will slightly enhance the CPU consumption for the decoding process at the receiver sides, it helps increasing the overall security level.

Alternatively, in case encoded packets with degree d = 1 are allowed, it may be provided that such packets (or, more generally, packets with degree of smaller than a configurable threshold) are fully encrypted by calculating E(X„ C) with E being an encryption transformation. For instance, the encryption transformation E might be the same cipher as the one employed for encrypting solely the coefficient vector C. It is to be noted that using, e.g., the robust soliton degree distribution, only a rather small fraction of the packets has to be encrypted in this conventional way. By this means it will be ensured that the attacker does not get any unencoded packet "for free", i.e. that an attacker's initial pool of known plaintext packets is P = 0, therefore increasing the overall security level for all transmitted encoded packets (also with degree d > 1 ) significantly. At the same time there is only a marginal increase of overhead due to the amount of data to be transmitted for sending and receiving (for instance, one could use a normal streamcipher for the encryption of all packets with degree d < T_enc) by still being able to encrypt for a large fraction of encoded packets, namely P d > Te_nc) = 1 - P{d < Tenc) , only the coefficient vectors and being flexible for in-network processing. In this connection it is to be recalled that in most settings \X\ » \C\ .

According to another preferred embodiment with respect to an improved security level a portion of additional bogus packets p_bogus may be generated and injected at the sending node. The goal of those packets is to lure the attacker into a wrong decoding. Such an approach requires the transmission of slightly more packets, as those bogus packets does not bring any information, therefore increasing the sending and receiving effort at any involved node. However, the pure decoding process at the final receiver nodes is not increased (excluding the decryption and subsequent skipping of packets p_bogus, E(C)). It is important to note that the receiver can detect and discard those packets. One way to recognize those packets is, e.g., to set the coefficient vector C to zero (which is never used for fountain codes), when transmitting those bogus packets. On the other hand, a possible attacker cannot recognize that the coefficient vector C is set to zero because C is encrypted over the wireless.

There are several ways how to design and further develop the teaching of the present invention in an advantageous way. To this end, it is to be referred to the patent claims subordinate to patent claim 1 on the one hand, and to the following explanation of a preferred example of an embodiment of the invention illustrated by the drawing on the other hand. In connection with the explanation of the preferred example of an embodiment of the invention by the aid of the drawing, generally preferred embodiments and further developments of the teaching will be explained. In the drawings the only

Fig. illustrates schematically a content distribution scenario with sending nodes, forwarding nodes and receiving nodes in which an encoding scheme according to the present invention can be applied.

The only Fig. illustrates a network the goal of which is to transmit large bulks of data which are fully available at the sender side S in a multi-hop manner to a multicast group that is represented by the receiving nodes R1 and R2. The network medium is considered to be noisy and highly error-proned which is the reason why the method according to the present invention is believed to be most promising in wireless environments. Nevertheless, to some extend it may also be advantageously in a wired setting. The network consists of n (wireless) nodes distributed in a delimited area. It is assumed that the set of nodes is partitioned into three distinct roles: source, forwarder, and receiver.

The only Fig. schematically depicts a simplified network including one sending node S, two forwarding nodes F1 and F2, as well as two receiving nodes R1 and R2. It is assumed that during the transmission of the data, the receivers R1 and R2 remain connected to the source S, possibly over several hops, e.g. over the forwarding nodes F1 and F2 depicted in the Fig. Generally, there can be several sources S, and forwarders F can come and go. Without loss of generality however, the Fig. illustrates a model with one source S only, and the network remains static. However, the method in accordance with the invention would also adapt to mobile networks such as VANETs very easily.

A flow of data is assumed to come from the source S to a set of receivers {R} (represented by receivers R1 and R2), and possibly propagated by a set of forwarders {F} (represented by forwarding nodes F1 and F2) A forwarder distincts itself from a receiver by the fact that it is not interested in the data, but cooperatively forwards it, such that eventually all the receivers R1 , R2 collect completely the data transmitted by the source S. Furthermore, a routing overlay may be available such that the diffusion of the data can be achieved efficiently. Such an overlay is build upon an interest for the data transmitted by the source S. To enhance the resiliency against eavesdroppers, a multi-path message propagation is advisable.

As illustrated in the Fig., the sending node S has the source data and a key k. The source data is divided into single plaintext packets Pi, from which the sender S generates payloads by means of encoding. The packets that sender S transmits over the wireless medium are each composed of one such payload X, and a coefficient vector C that carries the information on which of said plaintext packets Pi contributed to the encoding. According to the present invention, instead of encrypting the encoded packets, the sending node S encrypts the coefficient vector C and thus transmits X,E(C). X, E(C) is similar to E(X,C) insofar as without knowing C an eavesdropper cannot infer the meaning/content of plaintext information. However, the entropy of the source data should be relatively high, i.e. the predictability and/or redundancy of the source data should be relatively low, in order to avoid that an attacker could infer the source data from the encoded packet through statistical analysis.

To avoid giving up any flexibility regarding the composition of new and meaningful encoded packets on its way to the final destination R1 , R2, the encryption scheme E is chosen from a specific class of encryption transformation, namely a privacy homomorphism whose operator is the one used by the fountain code. Preferably the encryption transformation E is an additively homomorphic encryption transformation such that it holds E(a Θ b) = E(a) <S> E(b) for any plaintext pair a and b, a properly chosen additive operation <S> on the ciphertext, and another additive operation Θ on the plaintext.

By applying the described method the transmitted encoded packets are concealed, i.e. the secrecy of the data is preserved, by still ensuring that network coding is possible at intermediate nodes based on the received packets. Further, the encryption scheme supports ANY operation used in the network coding scheme itself. Moreover, it can prevent attacks on the network coding scheme itself, where the attacker inject packets in order to delay the decoding process. These attacks can decrease drastically the performance of the network.

Using this privacy homomorphism based encryption approach, the intermediary nodes F1 , F2 can still apply network coding on the packets it forwards, but have no indication of what they are transmitting. Defining the privacy homomorphism transformation E(p, k) and its "inverse" operation, which decrypts: D(e, k), for an instance of k and p, it then holds that: p = D(E(p, k), k) . Furthermore, the following homomorphism property holds: Θ p₂ = D(E(p^ ,k) ® E(p₂,k)) .

Now at the intermediary node, a node can combine two encrypted packets together thanks to the privacy homomorphic transformation. For example, if the intermediary node F1 had received: X^Ef^, ^) and X₂\\E(C₂, k₂) , it can combine them in one packet: X θ

k_x) ®> E{C₂, k₂) . The notation indicates that a homomorphic encryption scheme is applied which is symmetric and uses pairwise keys. However, without loss of generality the proposed encryption scheme also works with other homomorphic encryption schemes, e.g. symmetric and groupwise keys but also asymmetric homomorphic schemes.

At the end point sides, which possess the keys k_h receiving nodes R1 , R2 can call the decryption key, in order to retrieve the plaintext of the network encoded packet: X, Θ X₂ ||c, ® C₂ = X ® X₂ ||£>(E(C, ,k_t) ® E(C₂ , k₂ )), , k₂ ) .

Many modifications and other embodiments of the invention set forth herein will come to mind the one skilled in the art to which the invention pertains having the benefit of the teachings presented in the foregoing description and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed and that modifications and other embodiments are intended to be included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.

Claims

C l a i m s

1 . Method for network coding transmission from a sending node (S) to at least one receiving node (R1 , R2), possibly via one or more forwarding nodes (F1 , F2), wherein the transmission data is divided into single plaintext packets p_if wherein payloads X are generated from said plaintext packets Pi by means of encoding, and

wherein each of the packets being transmitted is composed of one of said payloads X, and a coefficient vector C that carries the information on which of said plaintext packets Pi contributed to the encoding,

c h a r a c t e r i z e d i n that, before transmitting a packet, said coefficient vector C is solely being encrypted.

2. Method according to claim 1 , wherein said coefficient vector C is encrypted by means of a homomorphic encryption scheme.

3. Method according to claim 1 or 2, wherein said coefficient vector C is encrypted by means of an additively homomorphic encryption transformation.

4. Method according to claim 3, wherein said forwarding nodes (F1 , F2) generate new encoded packets based on already received ones.

5. Method according to any of claims 1 to 4, wherein an exclusive OR (XOR) operation is employed for encoding.

6. Method according to any of claims 1 to 5, wherein said sending node (S) and said at least one receiving node (R1 , R2) share cryptographic material.

7. Method according to any of claims 2 to 6, wherein said homomorphic encryption scheme is symmetric and uses pairwise keys.

8. Method according to any of claims 1 to 7, wherein the degree distribution for the encoding is chosen to have a minimum degree d_min that is higher than one.

9. Method according to any of claims 1 to 7, wherein encoded packets with degree smaller than a configurable threshold are fully encrypted by calculating E(X„ C) with E being an encryption transformation.

10. Method according to claim 9, wherein said encryption transformation E is a stream cipher.

1 1 . Method according to any of claims 1 to 10, wherein a portion of additional bogus packets is generated and injected by said sending node (S).