# Group-Based Reduction Schemes for Streaming Applications

Authors: Riccardo Bernardini; Roberto Cesco Fabbro; Roberto Rinaldo
Journal: ISRN Communications and Networking
 (2011)

---

## Abstract

Some peer-to-peer streaming systems make use of linear codes to reduce the rate of the data uploaded by peers with limited upload capabilities. Such “data reduction” techniques are based on a vector-space approach and produce the data to be uploaded by means of linear combinations of the content data in a suitable finite field. In this paper, we propose a more general approach based on group theory. The
new approach, while including the vector space approach as a special case, allows to design schemes that cannot be modeled as linear codes. We analyze the properties of the schemes based on the new approach, showing also how a group-based scheme can be used to prevent stream poisoning and how a group-based scheme can be converted into a secret-sharing scheme. Examples of group-based schemes that cannot be described in the vector-space framework are also shown.


---

## Body

## 1. Introduction

A problem that is currently attracting attention in the research community is the problem of streaming live content to a large number of nodes. The main issue to be solved is due to the amount of upload bandwidth required to the server that, unless multicast is used, is equal to the bandwidth required by a single viewer multiplied by the number of viewers. Although multicast is a possible solution, it has its drawbacks too, especially if the audience is spread among several different autonomous systems (AS).An approach that recently attracted interest in the research community is the use of peer-to-peer (P2P) solutions. With the P2P approach, each viewer resends the received data to other users, and, ideally, if each user retransmitted the video to another user, the server would just need to “feed” a handful of nodes, and the network would take care of itself. Unfortunately, the application of the P2P paradigm to multimedia streaming has some difficulties. Maybe the most important one is due to the fact that the typical residential user have enoughdownload bandwidth to receive the stream but not enough upload bandwidth to retransmit it. This makes the application of the P2P paradigm to video streaming not trivial.Some peer-to-peer streaming systems [1–5] propose the use of linear codes (someone interprets this approach as an instance of network coding [6]) to overcome the asymmetric bandwidth problem. In order to adapt the upload bandwidth to the user capabilities, the node combines the content data by means of some linear combinations and forwards the result. If the node has a reduced upload bandwidth, the forwarded linear combinations will not be sufficient to recover the original content, but a node can contact more than one peer to receive different sets of linear combinations in order to be able to recover the content data.The approaches proposed in [1–5] reduce the required data rate by using linear codes obtained as linear transformations of vector spaces over a finite field. The goal of this paper is to introduce a more general approach on data rate reduction based on group theory. We will show that the classical vector space approach is just a specialization of the theory presented here, since vector spaces are just a special type of groups. However, since groups are more general than vector spaces, the theory presented in this paper allows one to create new coding procedures that cannot be described as linear combinations in suitable vector spaces. Note that the only hypothesis required is that the groups involved have a finite number of elements, and in particular, it is not required that the groups are commutative.Although the application that motivated this work was rate reduction for P2P streaming, we will show that the theory presented here has a wider application range and it allows, for example, the construction of systems that counteract poisoning attacks [7] or allow secret sharing [8, 9].This paper is organized as follows: in Section2, we introduce a formalism for group-based reduction schemes (GBRS), in Section 3, we study the properties of GBRS; in Section 4, we give some examples of GBRS that cannot be described with the vector space approach; in Section 5, we give the conclusions.


## 2. Group-Based Reduction Schemes

Some P2P systems for multimedia streaming solve the problem of the limited bandwidth of residential users by uploading, instead of the whole content, some linear combinations (in a suitable finite field) of the data that constitute the content [1–3, 5]. The goal of this section is to introduce an alternative description of this type of “data reduction” procedures not based, as usual, on vector spaces but on group theory. In order to make the introduction of the group theory approach easier, we first introduce (in Section 2.1) a very general formalization of the reduction process that will be specialized in Section 2.2 to the desired group-based formalization.For the sake of concreteness, we will refer to the peer-to-peer streaming application, but this does not prevent the application of the presented theory to other applicative contexts of network coding.


### 2.1. Data Reduction Schemes

We will model thecontent stream to be transmitted as a sequence of content symbols belonging to a finite content alphabetG. Each content symbol g∈G requires, clearly, log2|G| per element. The idea for reducing the rate necessary for the uploaded stream is to map every content symbol g to a reduced symbolu belonging to a smaller alphabet. Since the alphabet of u is smaller than G, the number of bits required for u will be smaller.Definition 1.
A reduction scheme is given via (i) a finite setS and (ii) a set of reduction functions rs:G→Ks,indexed by s∈S and sharing the same domain G (the content alphabet).Remark 1.
Note that no constraint is put onKs. In a practical context, it is expected that eachKshas smaller cardinality thanG.
A node with limited upload bandwidth chooses at startup areduction parameters∈S. Every time it receives a new content symbol g, it reduces it by processing it with the reduction function rs correspondent to the chosen s to obtain the reduced symbol(1)us:=rs(g),
that is encoded with log2|Ks|<log2|G| bits and sent to the other peers.
A node that wants to recover the original content symbolg contacts R peers, receives the corresponding reduced versions us1, us2,…,usR and recovers g by solving the system
(2)us1=rs1(g),us2=rs2(g),⋮usR=rsR(g).
Intuitively, if R is large enough, the peer can recover g. A key concept that we will use in this paper is the concept of a reduction scheme that it is R-recoverable. Informally, a scheme is R-recoverable if every g∈G can be recovered by the knowledge of any set of R different reduced versions.Definition 2 (R-recoverable).
Let{rs:G→Ks,s∈S} be a reduction scheme and define, for every set of R different reduction parameters s1,…, sR∈S, the function ϕs1,…,sR:G→Ks1×⋯×KsR as
(3)ϕs1,…,sR(g):=[rs1(g),…,rsR(g)].
The reduction scheme will be said to be R-recoverable if for every choice of R different parameters s1, …,sR∈S, function ϕs1,…,sR is injective.
The reduction scheme will be said to beR-tight if it is R-recoverable and for every choice of R-1 reduction parameters s1, …,sR-1∈S, the corresponding function ϕs1,…,sR-1 is not injective.Remark 2.
Note that in Definition2, we require only ϕs1,…,sR to be injective, notbijective. That is, we do not require that system (2) have a solution for every choice of usi∈Ksi, i=1,…,R (it could have none), but we require that if a solution exists, then it is unique.
The property of beingR-recoverable is very interesting for applicative purposes, since it allows each node to choose its parameter s at random while granting (with large probability) the possibility of recovering the content g, since the probability of having two nodes choosing the same value can be made as small as desired by choosing |S| large enough. A reduction scheme that is R-recoverable has also other interesting characteristics such as being resilient to data loss (if the node contacts N>R peer, it can recover g as soon as it receives R reduced versions out of N), counteracting poisoning [7] (the node uses R reduced versions to recover g and uses the remaining N-R to check for the correctness of the result [1]), and reducing jitter [10].Example 1 (Vandermonde reduction scheme).
In order to give a concrete example of the just described abstract model, it is worthwhile to show how the reduction approach in [1] can be adapted to the described setup. The approach in [1] maps a block of Rd bits of the content stream in a column vector
(4)c=[a1,…,aR]t,
where each ai belongs to the Galois field with 2d elements 𝔽2d. Each node chooses at start-up time an element s∈𝔽2d and constructs the row vector
(5)rs:=[1,s,…,sR-1].
In order to produce the reduced version of vector c, the node multiplies c by rs to obtain us=rsc. Value us is sent to the other peers, and its transmission requires only d bits instead of Rd bits. Therefore, the required upload bandwidth is R times smaller.
In order to recoverc, a node can ask for R different values us1,…,usR and solve the linear system
(6)[us1us2⋯usR]=[1s1⋯s1R-11s2⋯s2R-1⋮⋮⋮1sR⋯sRR-1]︸R[a1a2⋮aR]︸c.
Note that matrix R in (6) is a Vandermonde matrix, and it is invertible as soon as all the si values are different.
Reformulated with the language of the formalization presented here, we can say that the content alphabet is the set ofR-dimensional vectors with entries in 𝔽2d; that is, G=𝔽2dR; the reduction functions are parametrized by s∈S=𝔽2d and are defined as
(7)rs(c):=[1,s,…,sR-1]c,
and, finally, Ks=𝔽2d for every s∈S.
Note that this reduction scheme isR-tight.


### 2.2. Group-Based Reduction Procedures

The setup described in Section2.1 is very general. In order to simplify the study, it is worthwhile to restrict the model above by adding to it some structure. A structure that is quite powerful but still quite general to be applied in several cases of practical interest is the structure of group. In this paper, we need only basic notions and results of group theory. For the sake of completeness, Appendix A summarizes the concepts used in this paper, and a more detailed description can be found in the literature [11, 12].In the following we will denote the group operation as a product and will use the symbole for the neutral element of a group. We will denote with E={e} the trivial group that contains only the neutral element. Group isomorphism will be denoted with ≃. The ring of integers modulo N will be denoted as ℤ/Nℤ.Definition 3.
A group-based reduction scheme (GBRS) is a reduction scheme{rs:G→Ks,s∈S}, where the content alphabetG and each reduced alphabet Ks, s∈S are finite groups and each rs is a group epimorphism (that is, a surjective homomorphism). Note that there is no loss of generality in requiring that each rs is an epimorphism, since one can always replace Ks with Im(rs).Remark 3.
Note that the reduction scheme presented in Example1 is a group-based reduction scheme, since 𝔽2dR and 𝔽2d are groups (with respect to the sum) and maps rs(c)=rsc are clearly group homomorphisms. We will see in Section 4 examples of group-based schemes that are not based on a vector space structure.


#### 2.2.1. Normalized Form

According to Definition3, in order to specify a group-based scheme, one must specify the content group G, the reduced groups Ks, and the epimorphisms rs. These requirements can be simplified by exploiting the fundamental homomorphism theorem [11] that implies that rs can be written as(8)rs(x)=η(πker⁡(rs)(x)),
where πker(rs):G→G/ker(rs) is the natural map associated with G/ker(rs) [11] and η:G/ker(rs)→Im(rs)=Ks is an isomorphism. Since isomorphic groups are basically the same group, isomorphism η does not have any practical consequences in our context, so we can restrict ourselves to the case where reduced alphabets are quotient groups G/H, where H is a normal subgroup of G (the set of normal subgroups coincides with the set of subgroups that are kernel of some homomorphism [11]) and map r:G→G/H is the natural map of G in G/H (i.e., r(x)=xH, where xH is the coset of G/H to which x belongs) [11].Definition 4 (GBRS normalized form).
A group-based reduction scheme{rs:G→Ks,s∈S} is said to be in normalizedform if for every s∈S
(1)Ks=G/Hs for some Hs⊲G,
(2) maprs is the natural map πHs:G→G/Hs associated with G/Hs.
Observe that in order to specify a GBRS in normalized form, it suffices to specify a set{H1,H2,…,HL} of normal subgroups of G. With a minor abuse of language, we will use the term reduction scheme also for set {H1,H2,…,HL}.
With the normalized form, the reduced version of a content symbolg is always a coset gH which can be considered as “g reduced modulo H.” The group H represents the “uncertainty” that one has about g when it knows its reduced version gH: the smaller the cardinality of H, the smaller the uncertainty about g. If H=E, no uncertainty is present, and g is exactly known.Example 2.
It is worthwhile to describe the Vandermonde reduction scheme of Example1 as a GBRS in normalized form. The kernel of map rs(u)=rsu is the subspace of 𝔽2dR orthogonal to rs. The elements of the quotient group 𝔽2dR/ker(rs) are translated versions of the subspace orthogonal to rs. Note that every coset U of 𝔽2dR/ker(rs) is uniquely identified by the value of the product rsu, where u is any element of coset U (it is easy to see that the product does not depend on the chosen u).
Summarizing, valuers(u) can be computed as follows: first u is mapped to the coset u+ker(rs) to which it belongs, then any representative of the coset is left multiplied by rs. It is easy to verify that the latter step is an isomorphism from 𝔽2dR/ker(rs) to 𝔽2d. Therefore, in order to study the theoretical properties of the Vandermonde reduction scheme, one can replace each rs with the natural map πker(rs).


## 2.1. Data Reduction Schemes

We will model thecontent stream to be transmitted as a sequence of content symbols belonging to a finite content alphabetG. Each content symbol g∈G requires, clearly, log2|G| per element. The idea for reducing the rate necessary for the uploaded stream is to map every content symbol g to a reduced symbolu belonging to a smaller alphabet. Since the alphabet of u is smaller than G, the number of bits required for u will be smaller.Definition 1.
A reduction scheme is given via (i) a finite setS and (ii) a set of reduction functions rs:G→Ks,indexed by s∈S and sharing the same domain G (the content alphabet).Remark 1.
Note that no constraint is put onKs. In a practical context, it is expected that eachKshas smaller cardinality thanG.
A node with limited upload bandwidth chooses at startup areduction parameters∈S. Every time it receives a new content symbol g, it reduces it by processing it with the reduction function rs correspondent to the chosen s to obtain the reduced symbol(1)us:=rs(g),
that is encoded with log2|Ks|<log2|G| bits and sent to the other peers.
A node that wants to recover the original content symbolg contacts R peers, receives the corresponding reduced versions us1, us2,…,usR and recovers g by solving the system
(2)us1=rs1(g),us2=rs2(g),⋮usR=rsR(g).
Intuitively, if R is large enough, the peer can recover g. A key concept that we will use in this paper is the concept of a reduction scheme that it is R-recoverable. Informally, a scheme is R-recoverable if every g∈G can be recovered by the knowledge of any set of R different reduced versions.Definition 2 (R-recoverable).
Let{rs:G→Ks,s∈S} be a reduction scheme and define, for every set of R different reduction parameters s1,…, sR∈S, the function ϕs1,…,sR:G→Ks1×⋯×KsR as
(3)ϕs1,…,sR(g):=[rs1(g),…,rsR(g)].
The reduction scheme will be said to be R-recoverable if for every choice of R different parameters s1, …,sR∈S, function ϕs1,…,sR is injective.
The reduction scheme will be said to beR-tight if it is R-recoverable and for every choice of R-1 reduction parameters s1, …,sR-1∈S, the corresponding function ϕs1,…,sR-1 is not injective.Remark 2.
Note that in Definition2, we require only ϕs1,…,sR to be injective, notbijective. That is, we do not require that system (2) have a solution for every choice of usi∈Ksi, i=1,…,R (it could have none), but we require that if a solution exists, then it is unique.
The property of beingR-recoverable is very interesting for applicative purposes, since it allows each node to choose its parameter s at random while granting (with large probability) the possibility of recovering the content g, since the probability of having two nodes choosing the same value can be made as small as desired by choosing |S| large enough. A reduction scheme that is R-recoverable has also other interesting characteristics such as being resilient to data loss (if the node contacts N>R peer, it can recover g as soon as it receives R reduced versions out of N), counteracting poisoning [7] (the node uses R reduced versions to recover g and uses the remaining N-R to check for the correctness of the result [1]), and reducing jitter [10].Example 1 (Vandermonde reduction scheme).
In order to give a concrete example of the just described abstract model, it is worthwhile to show how the reduction approach in [1] can be adapted to the described setup. The approach in [1] maps a block of Rd bits of the content stream in a column vector
(4)c=[a1,…,aR]t,
where each ai belongs to the Galois field with 2d elements 𝔽2d. Each node chooses at start-up time an element s∈𝔽2d and constructs the row vector
(5)rs:=[1,s,…,sR-1].
In order to produce the reduced version of vector c, the node multiplies c by rs to obtain us=rsc. Value us is sent to the other peers, and its transmission requires only d bits instead of Rd bits. Therefore, the required upload bandwidth is R times smaller.
In order to recoverc, a node can ask for R different values us1,…,usR and solve the linear system
(6)[us1us2⋯usR]=[1s1⋯s1R-11s2⋯s2R-1⋮⋮⋮1sR⋯sRR-1]︸R[a1a2⋮aR]︸c.
Note that matrix R in (6) is a Vandermonde matrix, and it is invertible as soon as all the si values are different.
Reformulated with the language of the formalization presented here, we can say that the content alphabet is the set ofR-dimensional vectors with entries in 𝔽2d; that is, G=𝔽2dR; the reduction functions are parametrized by s∈S=𝔽2d and are defined as
(7)rs(c):=[1,s,…,sR-1]c,
and, finally, Ks=𝔽2d for every s∈S.
Note that this reduction scheme isR-tight.


## 2.2. Group-Based Reduction Procedures

The setup described in Section2.1 is very general. In order to simplify the study, it is worthwhile to restrict the model above by adding to it some structure. A structure that is quite powerful but still quite general to be applied in several cases of practical interest is the structure of group. In this paper, we need only basic notions and results of group theory. For the sake of completeness, Appendix A summarizes the concepts used in this paper, and a more detailed description can be found in the literature [11, 12].In the following we will denote the group operation as a product and will use the symbole for the neutral element of a group. We will denote with E={e} the trivial group that contains only the neutral element. Group isomorphism will be denoted with ≃. The ring of integers modulo N will be denoted as ℤ/Nℤ.Definition 3.
A group-based reduction scheme (GBRS) is a reduction scheme{rs:G→Ks,s∈S}, where the content alphabetG and each reduced alphabet Ks, s∈S are finite groups and each rs is a group epimorphism (that is, a surjective homomorphism). Note that there is no loss of generality in requiring that each rs is an epimorphism, since one can always replace Ks with Im(rs).Remark 3.
Note that the reduction scheme presented in Example1 is a group-based reduction scheme, since 𝔽2dR and 𝔽2d are groups (with respect to the sum) and maps rs(c)=rsc are clearly group homomorphisms. We will see in Section 4 examples of group-based schemes that are not based on a vector space structure.


### 2.2.1. Normalized Form

According to Definition3, in order to specify a group-based scheme, one must specify the content group G, the reduced groups Ks, and the epimorphisms rs. These requirements can be simplified by exploiting the fundamental homomorphism theorem [11] that implies that rs can be written as(8)rs(x)=η(πker⁡(rs)(x)),
where πker(rs):G→G/ker(rs) is the natural map associated with G/ker(rs) [11] and η:G/ker(rs)→Im(rs)=Ks is an isomorphism. Since isomorphic groups are basically the same group, isomorphism η does not have any practical consequences in our context, so we can restrict ourselves to the case where reduced alphabets are quotient groups G/H, where H is a normal subgroup of G (the set of normal subgroups coincides with the set of subgroups that are kernel of some homomorphism [11]) and map r:G→G/H is the natural map of G in G/H (i.e., r(x)=xH, where xH is the coset of G/H to which x belongs) [11].Definition 4 (GBRS normalized form).
A group-based reduction scheme{rs:G→Ks,s∈S} is said to be in normalizedform if for every s∈S
(1)Ks=G/Hs for some Hs⊲G,
(2) maprs is the natural map πHs:G→G/Hs associated with G/Hs.
Observe that in order to specify a GBRS in normalized form, it suffices to specify a set{H1,H2,…,HL} of normal subgroups of G. With a minor abuse of language, we will use the term reduction scheme also for set {H1,H2,…,HL}.
With the normalized form, the reduced version of a content symbolg is always a coset gH which can be considered as “g reduced modulo H.” The group H represents the “uncertainty” that one has about g when it knows its reduced version gH: the smaller the cardinality of H, the smaller the uncertainty about g. If H=E, no uncertainty is present, and g is exactly known.Example 2.
It is worthwhile to describe the Vandermonde reduction scheme of Example1 as a GBRS in normalized form. The kernel of map rs(u)=rsu is the subspace of 𝔽2dR orthogonal to rs. The elements of the quotient group 𝔽2dR/ker(rs) are translated versions of the subspace orthogonal to rs. Note that every coset U of 𝔽2dR/ker(rs) is uniquely identified by the value of the product rsu, where u is any element of coset U (it is easy to see that the product does not depend on the chosen u).
Summarizing, valuers(u) can be computed as follows: first u is mapped to the coset u+ker(rs) to which it belongs, then any representative of the coset is left multiplied by rs. It is easy to verify that the latter step is an isomorphism from 𝔽2dR/ker(rs) to 𝔽2d. Therefore, in order to study the theoretical properties of the Vandermonde reduction scheme, one can replace each rs with the natural map πker(rs).


## 2.2.1. Normalized Form

According to Definition3, in order to specify a group-based scheme, one must specify the content group G, the reduced groups Ks, and the epimorphisms rs. These requirements can be simplified by exploiting the fundamental homomorphism theorem [11] that implies that rs can be written as(8)rs(x)=η(πker⁡(rs)(x)),
where πker(rs):G→G/ker(rs) is the natural map associated with G/ker(rs) [11] and η:G/ker(rs)→Im(rs)=Ks is an isomorphism. Since isomorphic groups are basically the same group, isomorphism η does not have any practical consequences in our context, so we can restrict ourselves to the case where reduced alphabets are quotient groups G/H, where H is a normal subgroup of G (the set of normal subgroups coincides with the set of subgroups that are kernel of some homomorphism [11]) and map r:G→G/H is the natural map of G in G/H (i.e., r(x)=xH, where xH is the coset of G/H to which x belongs) [11].Definition 4 (GBRS normalized form).
A group-based reduction scheme{rs:G→Ks,s∈S} is said to be in normalizedform if for every s∈S
(1)Ks=G/Hs for some Hs⊲G,
(2) maprs is the natural map πHs:G→G/Hs associated with G/Hs.
Observe that in order to specify a GBRS in normalized form, it suffices to specify a set{H1,H2,…,HL} of normal subgroups of G. With a minor abuse of language, we will use the term reduction scheme also for set {H1,H2,…,HL}.
With the normalized form, the reduced version of a content symbolg is always a coset gH which can be considered as “g reduced modulo H.” The group H represents the “uncertainty” that one has about g when it knows its reduced version gH: the smaller the cardinality of H, the smaller the uncertainty about g. If H=E, no uncertainty is present, and g is exactly known.Example 2.
It is worthwhile to describe the Vandermonde reduction scheme of Example1 as a GBRS in normalized form. The kernel of map rs(u)=rsu is the subspace of 𝔽2dR orthogonal to rs. The elements of the quotient group 𝔽2dR/ker(rs) are translated versions of the subspace orthogonal to rs. Note that every coset U of 𝔽2dR/ker(rs) is uniquely identified by the value of the product rsu, where u is any element of coset U (it is easy to see that the product does not depend on the chosen u).
Summarizing, valuers(u) can be computed as follows: first u is mapped to the coset u+ker(rs) to which it belongs, then any representative of the coset is left multiplied by rs. It is easy to verify that the latter step is an isomorphism from 𝔽2dR/ker(rs) to 𝔽2d. Therefore, in order to study the theoretical properties of the Vandermonde reduction scheme, one can replace each rs with the natural map πker(rs).


## 3. Properties of GBRS

In this section, we will study some properties of GBRS. First, in Section3.1, we will derive conditions for the existence of a solution of system (2), and we will show that depending on the choice of the subgroups, system (2) could have no solution for some choice of the values usi. If a reduction scheme is such that some R-ple of reduced values is not admissible, one expects that the R-ple of reduced values that can be obtained has some redundancy within. This idea is further pursued in Section 3.1.2, where it is also shown that the redundancy can be used to counteract stream poisoning attacks [7].The Vandermonde reduction scheme described in Example1 is deeply linked with the secret sharing scheme of [13]. Actually, the secret sharing scheme of Shamir can be derived from the Vandermonde scheme by replacing some information data with random data. This idea is discussed in greater detail in Section 3.2, where it is shown how nonredundant reduction schemes (i.e., schemes such that (2) has always a solution for every R-ple of reduced values) can be easily converted in secret sharing schemes.


### 3.1. Reconstruction

As explained in Section2.1, recovering the original content requires to solve system (2). In this section, we are going to study the reconstruction problem by showing that given two reduced versions uH and vK, one can combine them in order to get a “virtual” reduced version w(H∩K), reduced with respect to the smaller uncertainty group H∩K. Intuitively, by combining the virtual reduced version with other reduced versions, one can make the uncertainty group smaller and smaller until the original content symbol is recovered. In some sense, this corresponds to solving system (2) by means of an iterative approach: first, we determine the set of values of g that satisfy the first two equations of (2), then we use the third equation to refine the solution, and so on until only one solution remains. The problem to be solved at the first step of the iterative algorithm can be formalized as follows.Problem 1.
LetH and K be normal subgroups of G, and let uH∈G/H and vK∈G/K. Find all the a∈G such that πH(a)=uH and πK(a)=vK (or, equivalently, find the intersection uH∩vK).
The following property gives an answer to Problem1.Property 1.
LetH and  K be normal subgroups of  G, and let  uH∈G/H and  vK∈G/K. Let
(9)S:={g∈G:πH(g)=uH,πK(g)=vK}
be the set of content symbols g∈G that have uH and vK as reduced versions.(1)
Set𝒮 is not empty if and only if
(10)u-1v∈HK,
or, equivalently, uHK=vHK∈G/HK. Note that since H⊂HK,… chosen to represent uH.(2)
if (10) is satisfied, set 𝒮 can be written as
(11)S=a(H∩K)∈G(H∩K),
where a is any element of 𝒮. In other words, 𝒮 is a coset of G/(H∩K).Proof.
Step 1 (If𝒮≠∅, then condition (10) holds).
Letg∈𝒮. Since πH(g)=uH and πK(g)=vK, there must exist h∈H and k∈K such that
(12)uh=g=vk,
that implies u-1v=hk-1∈HK, that is, (10).
Step 2 (If condition (10) holds, then 𝒮≠∅).
Ifu-1v∈HK, one can find h∈H and k∈K such that u-1v=hk. It follows that uh=vk-1. Since uh∈uH and vk-1∈vK, it follows that uh∈𝒮. Incidentally, note that if one knows how to decompose an element of HK into a product of an element of H and an element of K, this procedure allows to find a solution in 𝒮.
Step 3 (If𝒮≠∅, then (11) holds).
Define homomorphismϕ:G→G/H×G/K as ϕ(g)=(πH(g),πK(g)) and observe that 𝒮=ϕ-1(uH,vK), that is, 𝒮 is the inverse image of (uH,vK). Since ϕ is an homomorphism, it is known that (if 𝒮≠∅) ϕ-1(uH,vK) is a coset of G/ker(ϕ). The thesis will follow if one can prove that
(13)ker⁡(ϕ)=H∩K.
Equation (13) can be proved by observing that a∈ker(ϕ) if and only if πH(a)=H (i.e., equivalent to a∈H) and πK(a)=K (i.e., equivalent to a∈K).Several remarks about Property1 are in order.Remarks 3.1.
(1) Suppose system (2) has solutionĝ. Clearly, ĝ must necessarily belong to set (11) so that set (11) can be written as ĝ(H∩K). It follows that (11) is the reduced version of the solutionĝwith respect to groupH∩K. This implies that Property 1 can be applied to every step of the iterative algorithm outlined at the beginning of this section.
Note that the availability of an iterative algorithm that solves system (2) one equation at time can be interesting from an implementation point of view, since it allows to spread the computational burden over the time, updating the solution as soon as new data are received. Depending on the applicative context, this can be more convenient than waiting for all data to arrive before starting the reconstruction.
(2) Note that condition (10) poses a compatibility condition on the pair (uH,vK). Such a condition can, however, be trivially true if HK is equal to the whole group G. If HK is a proper subset of G, not every pair (uH,vK) is admissible, and this, intuitively, implies that there is some redundancy in the pair (uH,vK). This aspect will be discussed more in detail in Section 3.1.2.


#### 3.1.1. The Reconstruction Problem and the Lattice of Normal Subgroups

Property1 has a nice interpretation in the context of the lattice of the normal subgroups of G (see Appendix B for a brief summary about lattices and [11] for a more detailed exposition). According to Property 1, the uncertainty group H∩K of the combined version is the greatest lower bound H∧K of H and K (i.e., their first common descendant on the lattice graph), while the group associated with constraint (10) is the smallest upper bound H∨K (i.e., their first common ancestor on the lattice graph).Example 3.
Figure1 shows the lattice graph of the subspaces of 𝔽43, together with the subspaces involved in the Vandermonde reduction scheme. In the case of Figure 1, 𝔽4 is implemented as the polynomials with coefficients in ℤ/2ℤ modulo z2+z+1.
Each node in Figure1 is labeled with a basis of the space, and the elements of 𝔽4 are represented as integer numbers in {0,1,2,3} whose digits in the binary representation are the coefficients of the corresponding element of 𝔽4 (e.g., 3 corresponds to z+1). The top node, labeled with I, represents the whole space 𝔽43, while the bottom node, labeled with {0}, represents the trivial space.
As explained in Example2, the groups associated with the Vandermonde scheme are the R-1-dimensional subspaces orthogonal to vectors of type (5). In Figure 1, these vector spaces are 2-dimensional and correspond to the four nodes marked with a bold circle. In order to obtain the intersection of two of the spaces associated with the Vandermonde scheme, one needs to find the first common descendant of the two spaces. By considering all the six different unordered pairs of spaces, one obtains the six one-dimensional spaces marked with bold hexagons in Figure 1.
Note that any triple of spaces has as common descendant the trivial space{0}, coherently with the fact that the scheme is 3-recoverable. Moreover, any pair of spaces has as common ancestor, the whole space 𝔽43, coherently with the fact that system (6) is solvable for any vector [ub1,…,ubR] of reduced values.Figure 1
Lattice of the subspaces of𝔽43.


#### 3.1.2. Redundancy in a GBRS

It is worthwhile commenting about the meaning of constraint (10) in the context of network coding for peer-to-peer streaming. Remember that uH and vK represent two reduced versions received from two peers. According to Property 1, if uH and vK have been obtained by reducing the same content symbol g, then uH and vK are “compatible” according to (10). If HK≠G, constraint (10) is not trivial, and not all the pairs (uH,vK) are valid.Intuitively, this is very similar to the case when redundant bits are added to protect communications from errors. Actually, adding redundant bits to the information to be transmitted constrains the set of admissible sequences of bits, and if the received sequence does not satisfy the constraints induced by the redundant bits, the receiver can deduce that an error occurred. Here, similarly, ifuH and vK do not satisfy (10), we can deduce that at least one reduced value must be incorrect. In Section 3.1.3, it is shown how it is possible to exploit this possibility to counteract poisoning attacks when network coding is used for streaming over peer-to-peer networks.The idea that ifHK≠G, then some redundancy is present, is confirmed by the following result.Property 2.
Let the notation be as in Property1. The following equality holds:
(14)|GH∩K|=|GH||GK||GHK|-1.Proof.
SinceHK/K is isomorphic to H/(H∩K) [11], it follows that
(15)|HK||K|=|H||H∩K|.
By exploiting (15), one can write
(16)|GH∩K|=|G||H∩K|=|HK||G||H||K|=|G||H||G||K||HK||G|=|GH||GK||GHK|-1.By taking the logarithms of (14) and reorganizing, one obtains(17)log⁡2|GHK|=(log⁡2|GH|+log⁡2|GK|)-log⁡2|GH∩K|.
Observe that the sum in parenthesis represents the number of bits that we used to receive the two reduced versions, while the last term on the right-hand side of (17) can be interpreted as the number of bits necessary to describe the result of the combination of the two reduced versions. It follows that their difference can be interpreted as the “redundancy” of the system in the sense that it is the difference between the number of bits spent and the number of bits that we got after the combination. Note that if HK=G (the case when condition (10) is always verified), then the last term of (17) is zero; that is, no redundancy is added.Definition 5.
Scheme{H1,H2,…HK} will be said to be nonredundant if for every choice of different Hjn, n=0,…,L such that Hj1∩⋯∩HjL≠E, then Hj0(Hj1∩⋯∩HjL)=G.Example 4.
Consider the case of the Vandermonde reduction scheme. In this case,H and K are two spaces, of dimension R-1, orthogonal, respectively, to vectors r1 and r2. The intersection H∩K is the space of the vectors that are orthogonal to bothr1 and r2, and, as known, it has dimension R-2. In the Vandermonde scheme, product HK is the vector space sum r1⊥+r2⊥. Since spaces r1⊥ and r2⊥ have dimension R-1, their sum has dimension R (that corresponds to the no redundancy case HK=G) unless the two spaces coincide. Therefore, the Vandermonde scheme has no redundancy.
We will introduce in the following a reduction scheme based on the Chinese remainder theorem (CRT) that allows for the introduction of redundancy.


#### 3.1.3. Counteracting Stream Poisoning

One important security threat in P2P streaming is thestream poisoning attack where a node sends wrong packets on the P2P network with the objective of disrupting the communication [7]. A reduction-based approach can help counteracting this attack. The idea is very simple: if the reduction scheme is R-recoverable, a node asks data to N>R peers, uses R reduced versions to recover the content, and then uses the remaining N-R reduced versions to check the correctness of the result; by the knowledge of which tests fail, it is possible to spot who tried the attack [1] (if all the tests fail, it means that a corrupted value was used in the reconstruction process; the node can retry the tests using a different subset of R in the reconstruction step). It is possible to show that this test is robust against a coordinated attack of at most N-R peers [1].A drawback of the test above is that one needs to recover first the content symbol and then do the test. If, by chance, a corrupted value is used in the reconstruction process, the node needs to try the reconstruction again. It would be more efficient if the node was able to spot the corrupted databefore doing the reconstruction process.This can be done by using a redundant scheme and exploiting Property1 by checking (10) before attempting the reconstruction.


### 3.2. Generalized Secret Sharing

Secret-sharing techniques allow one to share a secret amongN people with the constraint that (i) R people, putting their information together, can recover the secret and (ii) R-1 people that put their information together cannot deduce anything about the secret [8, 13]. We will say that the scheme achieves perfect secrecy. Note that secret sharing is a problem very similar to the reduction problem described in this paper but with the additional constraint of (ii).Actually, the Vandermonde reduction scheme described in Example1 can be easily converted into the secret-sharing scheme described in [8, 13]. More precisely, suppose that the secret to be shared is represented by a value x∈𝔽2d. The scheme of [13] builds vector c in (4) by setting a1=x and choosing a2,…,aR at random. Successively, N reduced values are created and distributed among the participants. In order to recover the secret, one collects R reduced versions, gets c by solving (6), and takes the first component of the result. Note that taking the first component of c is equivalent to right-multiplying c by e1t=[1,0,…,0].As said above, secret sharing has the additional constraint of perfect secrecy; that is, any set ofR-1 participants cannot deduce anything about the secret. This can be easily verified by observing that e1 does not belong to the space generated by any set of R-1 vectors of type rs, s≠0 (note that e1=r0), and this implies that from the knowledge of R-1 reduced values, nothing can be inferred about the value of x=a1=e1c.In this section we will show how the procedure used to convert the Vandermonde scheme into a secret sharing scheme can be generalized to any GBRS. Observe that the above described secret sharing procedure can be reformulated as follows: map the information to be sharedx into a vector v=xe1 belonging to the one-dimensional space V1:=span{e1} generated by e1, successively add to v a random vector q belonging to the R-1-dimensional space e1⊥ orthogonal to e1, and finally vector v+q is processed with the reduction scheme. The fact that the intersection between V1 and e1⊥ is trivial allows one to recover uniquely v (and x) from v+q.In order to extend the secrete sharing scheme in the GBRS context, we need anobfuscating subgroupM⊲G that will play the role of e1⊥.The generalized secret sharing scheme is the following: letI be any set of representatives of G/M; we encode the information to be shared as an element v∈I, we draw at random q∈M and compute h=vq∈vM, then we apply the reduction scheme to h. After recovering h, one can obtain v by applying πM, the natural map associated with M, to h. The only thing that remains to be checked is to verify when this scheme achieves perfect secrecy. Remember that a reduced value is a coset of a quotient group G/H, where H is a normal subgroup of G. Let uH be the reduced version of h=vq, with q a random element of M. Our objective is to deduce some information about v from the knowledge of uH. We will say that a value ℓ∈G is compatible withuH if there are m∈M and k∈H such that ℓm=uk, or, alternatively,(18)l∈uHM.
Note that if ℓ is not compatible with uH, then we obtain some information about the secret value, since we know that the secret cannot be ℓ. Therefore, the scheme will achieve perfect secrecy with reduction groupH if every ℓ∈I is compatible with uH for every u∈G.Remark 4.
From (18), it follows at once that ℓ is compatible with uH if and only if any other element of ℓM is compatible with uH. This implies that one can change the set of representatives I without changing the secrecy characteristics of the scheme.Definition 6.
LetH and M be normal subgroups of G. We say that perfect secrecy is achieved if for every u∈G, every ℓ∈I is compatible with uH.Property 3.
LetH and  M be normal subgroups of  G. Perfect secrecy is achieved if and only if  HM=G.Proof.
IfHM=G, then perfect secrecy is achieved. If HM=G, it is obvious that ℓ∈uHM=uG=G for every ℓ∈I.
IfHM≠G, then perfect secrecy is not achieved. Suppose now that HM≠G; that is, there is o∈G that does not belong to HM. Observe that according to Remark 4, we can suppose without loss of generality, e∈I; we will prove that e is not compatible with o-1. Indeed, if e was compatible with o, (18) would imply o∈HM. Therefore, e is not compatible with o-1, and perfect secrecy is not achieved.If conditionHM=G is fulfilled, it is possible to prove that perfect secrecy is achieved even in a stronger, information theoretical sense. Indeed, although Property 3 claims that if HM=G, then any uH can be obtained from any information symbol ℓ∈I, it could happen that the probability of obtaining uH from ℓ could depend on ℓ. In this case, an attacker could deduce from uH something about ℓ. The following result shows that this is not the case.Property 4.
LetL be a random variable assuming values in I, and let Q be a random variables assuming values in M and uniformly distributed. If HM=G, then for every α∈G,
(19)P[πH(LQ)=αH∣L=l]=|H∩M||M|.
According to Property 4, πH(LQ), the reduced version of LQ, is statistically independent on L, and this implies that mutual information I(πH(LQ);L) [14] is zero, so that an attacker cannot deduce anything about L from πH(LQ).The proof of Property4 is simplified by using the following lemma.Lemma 1.
Letβ∈G. If HM=G, cardinality Cβ:=|(βH)∩M| does not depend on β.Proof.
Step 1 (Ifh∈H, then Cβ=Cβh).
This follows at once by observing thatβH=βhH.Step 2 (Ifm∈M, thenCmβ=Cβ).
This follows at once by observing thatm[(βH)∩M]=(mβH)∩mM=(mβH)∩M.Step 3 (Cβ=Cefor everyβ∈G).
Since bothM and 0 are normal subgroups of G, MH=HM=G. It follows that every β∈G can be written as β=mh with m∈M and h∈H. By exploiting Steps 1 and 2 above, one deduces that
(20)Cβ=Cmh=Ch=Ce.Proof of Property4.
It is a simple verification(21)P[πH(LQ)=αH∣L=l]=P[LQ∈αH∣L=l]BydefinitionofπH=P[lQ∈αH∣L=l]=P[Q∈l-1αH∣L=l]=P[Q∈l-1αH]IndependenceofLandQ=P[Q∈(l-1αH)∩M]SinceQ∈M=|(l-1αH)∩M||M|Quniformlydistributed=|H∩M||M|Lemma1.One can interpret Property3 by saying that in order to have perfect secrecy, one must choose M large enough so that, when combined with any H that can result from the combining process, it generates the whole group G. This is what is done in the secret sharing scheme based on the Vandermonde scheme. In this case, M is a space of dimension R-1 that when combined with any nontrivial space resulting from the Vandermonde scheme, it generates the whole space 𝔽2dR.Property 5.
Let{H0,H1,H2,…HK} be a nonredundant  R-recoverable reduction scheme with  R≤K. Obfuscating group  M=H0 together with reduction scheme  {H1,H2,…HK} is a secret-sharing scheme that achieves perfect secrecy.Proof.
Since scheme{H0,H1,…HK} is not redundant, then we have, by definition, H0(Hj1∩⋯∩HjL)=G as soon as Hj1∩⋯∩HjL≠E.According to Property5, constructing secret-sharing schemes that achieve perfect secrecy is simple as soon as one has a nonredundant scheme with enough subgroups: just use one of the subgroups as the obfuscating group.


## 3.1. Reconstruction

As explained in Section2.1, recovering the original content requires to solve system (2). In this section, we are going to study the reconstruction problem by showing that given two reduced versions uH and vK, one can combine them in order to get a “virtual” reduced version w(H∩K), reduced with respect to the smaller uncertainty group H∩K. Intuitively, by combining the virtual reduced version with other reduced versions, one can make the uncertainty group smaller and smaller until the original content symbol is recovered. In some sense, this corresponds to solving system (2) by means of an iterative approach: first, we determine the set of values of g that satisfy the first two equations of (2), then we use the third equation to refine the solution, and so on until only one solution remains. The problem to be solved at the first step of the iterative algorithm can be formalized as follows.Problem 1.
LetH and K be normal subgroups of G, and let uH∈G/H and vK∈G/K. Find all the a∈G such that πH(a)=uH and πK(a)=vK (or, equivalently, find the intersection uH∩vK).
The following property gives an answer to Problem1.Property 1.
LetH and  K be normal subgroups of  G, and let  uH∈G/H and  vK∈G/K. Let
(9)S:={g∈G:πH(g)=uH,πK(g)=vK}
be the set of content symbols g∈G that have uH and vK as reduced versions.(1)
Set𝒮 is not empty if and only if
(10)u-1v∈HK,
or, equivalently, uHK=vHK∈G/HK. Note that since H⊂HK,… chosen to represent uH.(2)
if (10) is satisfied, set 𝒮 can be written as
(11)S=a(H∩K)∈G(H∩K),
where a is any element of 𝒮. In other words, 𝒮 is a coset of G/(H∩K).Proof.
Step 1 (If𝒮≠∅, then condition (10) holds).
Letg∈𝒮. Since πH(g)=uH and πK(g)=vK, there must exist h∈H and k∈K such that
(12)uh=g=vk,
that implies u-1v=hk-1∈HK, that is, (10).
Step 2 (If condition (10) holds, then 𝒮≠∅).
Ifu-1v∈HK, one can find h∈H and k∈K such that u-1v=hk. It follows that uh=vk-1. Since uh∈uH and vk-1∈vK, it follows that uh∈𝒮. Incidentally, note that if one knows how to decompose an element of HK into a product of an element of H and an element of K, this procedure allows to find a solution in 𝒮.
Step 3 (If𝒮≠∅, then (11) holds).
Define homomorphismϕ:G→G/H×G/K as ϕ(g)=(πH(g),πK(g)) and observe that 𝒮=ϕ-1(uH,vK), that is, 𝒮 is the inverse image of (uH,vK). Since ϕ is an homomorphism, it is known that (if 𝒮≠∅) ϕ-1(uH,vK) is a coset of G/ker(ϕ). The thesis will follow if one can prove that
(13)ker⁡(ϕ)=H∩K.
Equation (13) can be proved by observing that a∈ker(ϕ) if and only if πH(a)=H (i.e., equivalent to a∈H) and πK(a)=K (i.e., equivalent to a∈K).Several remarks about Property1 are in order.Remarks 3.1.
(1) Suppose system (2) has solutionĝ. Clearly, ĝ must necessarily belong to set (11) so that set (11) can be written as ĝ(H∩K). It follows that (11) is the reduced version of the solutionĝwith respect to groupH∩K. This implies that Property 1 can be applied to every step of the iterative algorithm outlined at the beginning of this section.
Note that the availability of an iterative algorithm that solves system (2) one equation at time can be interesting from an implementation point of view, since it allows to spread the computational burden over the time, updating the solution as soon as new data are received. Depending on the applicative context, this can be more convenient than waiting for all data to arrive before starting the reconstruction.
(2) Note that condition (10) poses a compatibility condition on the pair (uH,vK). Such a condition can, however, be trivially true if HK is equal to the whole group G. If HK is a proper subset of G, not every pair (uH,vK) is admissible, and this, intuitively, implies that there is some redundancy in the pair (uH,vK). This aspect will be discussed more in detail in Section 3.1.2.


### 3.1.1. The Reconstruction Problem and the Lattice of Normal Subgroups

Property1 has a nice interpretation in the context of the lattice of the normal subgroups of G (see Appendix B for a brief summary about lattices and [11] for a more detailed exposition). According to Property 1, the uncertainty group H∩K of the combined version is the greatest lower bound H∧K of H and K (i.e., their first common descendant on the lattice graph), while the group associated with constraint (10) is the smallest upper bound H∨K (i.e., their first common ancestor on the lattice graph).Example 3.
Figure1 shows the lattice graph of the subspaces of 𝔽43, together with the subspaces involved in the Vandermonde reduction scheme. In the case of Figure 1, 𝔽4 is implemented as the polynomials with coefficients in ℤ/2ℤ modulo z2+z+1.
Each node in Figure1 is labeled with a basis of the space, and the elements of 𝔽4 are represented as integer numbers in {0,1,2,3} whose digits in the binary representation are the coefficients of the corresponding element of 𝔽4 (e.g., 3 corresponds to z+1). The top node, labeled with I, represents the whole space 𝔽43, while the bottom node, labeled with {0}, represents the trivial space.
As explained in Example2, the groups associated with the Vandermonde scheme are the R-1-dimensional subspaces orthogonal to vectors of type (5). In Figure 1, these vector spaces are 2-dimensional and correspond to the four nodes marked with a bold circle. In order to obtain the intersection of two of the spaces associated with the Vandermonde scheme, one needs to find the first common descendant of the two spaces. By considering all the six different unordered pairs of spaces, one obtains the six one-dimensional spaces marked with bold hexagons in Figure 1.
Note that any triple of spaces has as common descendant the trivial space{0}, coherently with the fact that the scheme is 3-recoverable. Moreover, any pair of spaces has as common ancestor, the whole space 𝔽43, coherently with the fact that system (6) is solvable for any vector [ub1,…,ubR] of reduced values.Figure 1
Lattice of the subspaces of𝔽43.


### 3.1.2. Redundancy in a GBRS

It is worthwhile commenting about the meaning of constraint (10) in the context of network coding for peer-to-peer streaming. Remember that uH and vK represent two reduced versions received from two peers. According to Property 1, if uH and vK have been obtained by reducing the same content symbol g, then uH and vK are “compatible” according to (10). If HK≠G, constraint (10) is not trivial, and not all the pairs (uH,vK) are valid.Intuitively, this is very similar to the case when redundant bits are added to protect communications from errors. Actually, adding redundant bits to the information to be transmitted constrains the set of admissible sequences of bits, and if the received sequence does not satisfy the constraints induced by the redundant bits, the receiver can deduce that an error occurred. Here, similarly, ifuH and vK do not satisfy (10), we can deduce that at least one reduced value must be incorrect. In Section 3.1.3, it is shown how it is possible to exploit this possibility to counteract poisoning attacks when network coding is used for streaming over peer-to-peer networks.The idea that ifHK≠G, then some redundancy is present, is confirmed by the following result.Property 2.
Let the notation be as in Property1. The following equality holds:
(14)|GH∩K|=|GH||GK||GHK|-1.Proof.
SinceHK/K is isomorphic to H/(H∩K) [11], it follows that
(15)|HK||K|=|H||H∩K|.
By exploiting (15), one can write
(16)|GH∩K|=|G||H∩K|=|HK||G||H||K|=|G||H||G||K||HK||G|=|GH||GK||GHK|-1.By taking the logarithms of (14) and reorganizing, one obtains(17)log⁡2|GHK|=(log⁡2|GH|+log⁡2|GK|)-log⁡2|GH∩K|.
Observe that the sum in parenthesis represents the number of bits that we used to receive the two reduced versions, while the last term on the right-hand side of (17) can be interpreted as the number of bits necessary to describe the result of the combination of the two reduced versions. It follows that their difference can be interpreted as the “redundancy” of the system in the sense that it is the difference between the number of bits spent and the number of bits that we got after the combination. Note that if HK=G (the case when condition (10) is always verified), then the last term of (17) is zero; that is, no redundancy is added.Definition 5.
Scheme{H1,H2,…HK} will be said to be nonredundant if for every choice of different Hjn, n=0,…,L such that Hj1∩⋯∩HjL≠E, then Hj0(Hj1∩⋯∩HjL)=G.Example 4.
Consider the case of the Vandermonde reduction scheme. In this case,H and K are two spaces, of dimension R-1, orthogonal, respectively, to vectors r1 and r2. The intersection H∩K is the space of the vectors that are orthogonal to bothr1 and r2, and, as known, it has dimension R-2. In the Vandermonde scheme, product HK is the vector space sum r1⊥+r2⊥. Since spaces r1⊥ and r2⊥ have dimension R-1, their sum has dimension R (that corresponds to the no redundancy case HK=G) unless the two spaces coincide. Therefore, the Vandermonde scheme has no redundancy.
We will introduce in the following a reduction scheme based on the Chinese remainder theorem (CRT) that allows for the introduction of redundancy.


### 3.1.3. Counteracting Stream Poisoning

One important security threat in P2P streaming is thestream poisoning attack where a node sends wrong packets on the P2P network with the objective of disrupting the communication [7]. A reduction-based approach can help counteracting this attack. The idea is very simple: if the reduction scheme is R-recoverable, a node asks data to N>R peers, uses R reduced versions to recover the content, and then uses the remaining N-R reduced versions to check the correctness of the result; by the knowledge of which tests fail, it is possible to spot who tried the attack [1] (if all the tests fail, it means that a corrupted value was used in the reconstruction process; the node can retry the tests using a different subset of R in the reconstruction step). It is possible to show that this test is robust against a coordinated attack of at most N-R peers [1].A drawback of the test above is that one needs to recover first the content symbol and then do the test. If, by chance, a corrupted value is used in the reconstruction process, the node needs to try the reconstruction again. It would be more efficient if the node was able to spot the corrupted databefore doing the reconstruction process.This can be done by using a redundant scheme and exploiting Property1 by checking (10) before attempting the reconstruction.


## 3.1.1. The Reconstruction Problem and the Lattice of Normal Subgroups

Property1 has a nice interpretation in the context of the lattice of the normal subgroups of G (see Appendix B for a brief summary about lattices and [11] for a more detailed exposition). According to Property 1, the uncertainty group H∩K of the combined version is the greatest lower bound H∧K of H and K (i.e., their first common descendant on the lattice graph), while the group associated with constraint (10) is the smallest upper bound H∨K (i.e., their first common ancestor on the lattice graph).Example 3.
Figure1 shows the lattice graph of the subspaces of 𝔽43, together with the subspaces involved in the Vandermonde reduction scheme. In the case of Figure 1, 𝔽4 is implemented as the polynomials with coefficients in ℤ/2ℤ modulo z2+z+1.
Each node in Figure1 is labeled with a basis of the space, and the elements of 𝔽4 are represented as integer numbers in {0,1,2,3} whose digits in the binary representation are the coefficients of the corresponding element of 𝔽4 (e.g., 3 corresponds to z+1). The top node, labeled with I, represents the whole space 𝔽43, while the bottom node, labeled with {0}, represents the trivial space.
As explained in Example2, the groups associated with the Vandermonde scheme are the R-1-dimensional subspaces orthogonal to vectors of type (5). In Figure 1, these vector spaces are 2-dimensional and correspond to the four nodes marked with a bold circle. In order to obtain the intersection of two of the spaces associated with the Vandermonde scheme, one needs to find the first common descendant of the two spaces. By considering all the six different unordered pairs of spaces, one obtains the six one-dimensional spaces marked with bold hexagons in Figure 1.
Note that any triple of spaces has as common descendant the trivial space{0}, coherently with the fact that the scheme is 3-recoverable. Moreover, any pair of spaces has as common ancestor, the whole space 𝔽43, coherently with the fact that system (6) is solvable for any vector [ub1,…,ubR] of reduced values.Figure 1
Lattice of the subspaces of𝔽43.


## 3.1.2. Redundancy in a GBRS

It is worthwhile commenting about the meaning of constraint (10) in the context of network coding for peer-to-peer streaming. Remember that uH and vK represent two reduced versions received from two peers. According to Property 1, if uH and vK have been obtained by reducing the same content symbol g, then uH and vK are “compatible” according to (10). If HK≠G, constraint (10) is not trivial, and not all the pairs (uH,vK) are valid.Intuitively, this is very similar to the case when redundant bits are added to protect communications from errors. Actually, adding redundant bits to the information to be transmitted constrains the set of admissible sequences of bits, and if the received sequence does not satisfy the constraints induced by the redundant bits, the receiver can deduce that an error occurred. Here, similarly, ifuH and vK do not satisfy (10), we can deduce that at least one reduced value must be incorrect. In Section 3.1.3, it is shown how it is possible to exploit this possibility to counteract poisoning attacks when network coding is used for streaming over peer-to-peer networks.The idea that ifHK≠G, then some redundancy is present, is confirmed by the following result.Property 2.
Let the notation be as in Property1. The following equality holds:
(14)|GH∩K|=|GH||GK||GHK|-1.Proof.
SinceHK/K is isomorphic to H/(H∩K) [11], it follows that
(15)|HK||K|=|H||H∩K|.
By exploiting (15), one can write
(16)|GH∩K|=|G||H∩K|=|HK||G||H||K|=|G||H||G||K||HK||G|=|GH||GK||GHK|-1.By taking the logarithms of (14) and reorganizing, one obtains(17)log⁡2|GHK|=(log⁡2|GH|+log⁡2|GK|)-log⁡2|GH∩K|.
Observe that the sum in parenthesis represents the number of bits that we used to receive the two reduced versions, while the last term on the right-hand side of (17) can be interpreted as the number of bits necessary to describe the result of the combination of the two reduced versions. It follows that their difference can be interpreted as the “redundancy” of the system in the sense that it is the difference between the number of bits spent and the number of bits that we got after the combination. Note that if HK=G (the case when condition (10) is always verified), then the last term of (17) is zero; that is, no redundancy is added.Definition 5.
Scheme{H1,H2,…HK} will be said to be nonredundant if for every choice of different Hjn, n=0,…,L such that Hj1∩⋯∩HjL≠E, then Hj0(Hj1∩⋯∩HjL)=G.Example 4.
Consider the case of the Vandermonde reduction scheme. In this case,H and K are two spaces, of dimension R-1, orthogonal, respectively, to vectors r1 and r2. The intersection H∩K is the space of the vectors that are orthogonal to bothr1 and r2, and, as known, it has dimension R-2. In the Vandermonde scheme, product HK is the vector space sum r1⊥+r2⊥. Since spaces r1⊥ and r2⊥ have dimension R-1, their sum has dimension R (that corresponds to the no redundancy case HK=G) unless the two spaces coincide. Therefore, the Vandermonde scheme has no redundancy.
We will introduce in the following a reduction scheme based on the Chinese remainder theorem (CRT) that allows for the introduction of redundancy.


## 3.1.3. Counteracting Stream Poisoning

One important security threat in P2P streaming is thestream poisoning attack where a node sends wrong packets on the P2P network with the objective of disrupting the communication [7]. A reduction-based approach can help counteracting this attack. The idea is very simple: if the reduction scheme is R-recoverable, a node asks data to N>R peers, uses R reduced versions to recover the content, and then uses the remaining N-R reduced versions to check the correctness of the result; by the knowledge of which tests fail, it is possible to spot who tried the attack [1] (if all the tests fail, it means that a corrupted value was used in the reconstruction process; the node can retry the tests using a different subset of R in the reconstruction step). It is possible to show that this test is robust against a coordinated attack of at most N-R peers [1].A drawback of the test above is that one needs to recover first the content symbol and then do the test. If, by chance, a corrupted value is used in the reconstruction process, the node needs to try the reconstruction again. It would be more efficient if the node was able to spot the corrupted databefore doing the reconstruction process.This can be done by using a redundant scheme and exploiting Property1 by checking (10) before attempting the reconstruction.


## 3.2. Generalized Secret Sharing

Secret-sharing techniques allow one to share a secret amongN people with the constraint that (i) R people, putting their information together, can recover the secret and (ii) R-1 people that put their information together cannot deduce anything about the secret [8, 13]. We will say that the scheme achieves perfect secrecy. Note that secret sharing is a problem very similar to the reduction problem described in this paper but with the additional constraint of (ii).Actually, the Vandermonde reduction scheme described in Example1 can be easily converted into the secret-sharing scheme described in [8, 13]. More precisely, suppose that the secret to be shared is represented by a value x∈𝔽2d. The scheme of [13] builds vector c in (4) by setting a1=x and choosing a2,…,aR at random. Successively, N reduced values are created and distributed among the participants. In order to recover the secret, one collects R reduced versions, gets c by solving (6), and takes the first component of the result. Note that taking the first component of c is equivalent to right-multiplying c by e1t=[1,0,…,0].As said above, secret sharing has the additional constraint of perfect secrecy; that is, any set ofR-1 participants cannot deduce anything about the secret. This can be easily verified by observing that e1 does not belong to the space generated by any set of R-1 vectors of type rs, s≠0 (note that e1=r0), and this implies that from the knowledge of R-1 reduced values, nothing can be inferred about the value of x=a1=e1c.In this section we will show how the procedure used to convert the Vandermonde scheme into a secret sharing scheme can be generalized to any GBRS. Observe that the above described secret sharing procedure can be reformulated as follows: map the information to be sharedx into a vector v=xe1 belonging to the one-dimensional space V1:=span{e1} generated by e1, successively add to v a random vector q belonging to the R-1-dimensional space e1⊥ orthogonal to e1, and finally vector v+q is processed with the reduction scheme. The fact that the intersection between V1 and e1⊥ is trivial allows one to recover uniquely v (and x) from v+q.In order to extend the secrete sharing scheme in the GBRS context, we need anobfuscating subgroupM⊲G that will play the role of e1⊥.The generalized secret sharing scheme is the following: letI be any set of representatives of G/M; we encode the information to be shared as an element v∈I, we draw at random q∈M and compute h=vq∈vM, then we apply the reduction scheme to h. After recovering h, one can obtain v by applying πM, the natural map associated with M, to h. The only thing that remains to be checked is to verify when this scheme achieves perfect secrecy. Remember that a reduced value is a coset of a quotient group G/H, where H is a normal subgroup of G. Let uH be the reduced version of h=vq, with q a random element of M. Our objective is to deduce some information about v from the knowledge of uH. We will say that a value ℓ∈G is compatible withuH if there are m∈M and k∈H such that ℓm=uk, or, alternatively,(18)l∈uHM.
Note that if ℓ is not compatible with uH, then we obtain some information about the secret value, since we know that the secret cannot be ℓ. Therefore, the scheme will achieve perfect secrecy with reduction groupH if every ℓ∈I is compatible with uH for every u∈G.Remark 4.
From (18), it follows at once that ℓ is compatible with uH if and only if any other element of ℓM is compatible with uH. This implies that one can change the set of representatives I without changing the secrecy characteristics of the scheme.Definition 6.
LetH and M be normal subgroups of G. We say that perfect secrecy is achieved if for every u∈G, every ℓ∈I is compatible with uH.Property 3.
LetH and  M be normal subgroups of  G. Perfect secrecy is achieved if and only if  HM=G.Proof.
IfHM=G, then perfect secrecy is achieved. If HM=G, it is obvious that ℓ∈uHM=uG=G for every ℓ∈I.
IfHM≠G, then perfect secrecy is not achieved. Suppose now that HM≠G; that is, there is o∈G that does not belong to HM. Observe that according to Remark 4, we can suppose without loss of generality, e∈I; we will prove that e is not compatible with o-1. Indeed, if e was compatible with o, (18) would imply o∈HM. Therefore, e is not compatible with o-1, and perfect secrecy is not achieved.If conditionHM=G is fulfilled, it is possible to prove that perfect secrecy is achieved even in a stronger, information theoretical sense. Indeed, although Property 3 claims that if HM=G, then any uH can be obtained from any information symbol ℓ∈I, it could happen that the probability of obtaining uH from ℓ could depend on ℓ. In this case, an attacker could deduce from uH something about ℓ. The following result shows that this is not the case.Property 4.
LetL be a random variable assuming values in I, and let Q be a random variables assuming values in M and uniformly distributed. If HM=G, then for every α∈G,
(19)P[πH(LQ)=αH∣L=l]=|H∩M||M|.
According to Property 4, πH(LQ), the reduced version of LQ, is statistically independent on L, and this implies that mutual information I(πH(LQ);L) [14] is zero, so that an attacker cannot deduce anything about L from πH(LQ).The proof of Property4 is simplified by using the following lemma.Lemma 1.
Letβ∈G. If HM=G, cardinality Cβ:=|(βH)∩M| does not depend on β.Proof.
Step 1 (Ifh∈H, then Cβ=Cβh).
This follows at once by observing thatβH=βhH.Step 2 (Ifm∈M, thenCmβ=Cβ).
This follows at once by observing thatm[(βH)∩M]=(mβH)∩mM=(mβH)∩M.Step 3 (Cβ=Cefor everyβ∈G).
Since bothM and 0 are normal subgroups of G, MH=HM=G. It follows that every β∈G can be written as β=mh with m∈M and h∈H. By exploiting Steps 1 and 2 above, one deduces that
(20)Cβ=Cmh=Ch=Ce.Proof of Property4.
It is a simple verification(21)P[πH(LQ)=αH∣L=l]=P[LQ∈αH∣L=l]BydefinitionofπH=P[lQ∈αH∣L=l]=P[Q∈l-1αH∣L=l]=P[Q∈l-1αH]IndependenceofLandQ=P[Q∈(l-1αH)∩M]SinceQ∈M=|(l-1αH)∩M||M|Quniformlydistributed=|H∩M||M|Lemma1.One can interpret Property3 by saying that in order to have perfect secrecy, one must choose M large enough so that, when combined with any H that can result from the combining process, it generates the whole group G. This is what is done in the secret sharing scheme based on the Vandermonde scheme. In this case, M is a space of dimension R-1 that when combined with any nontrivial space resulting from the Vandermonde scheme, it generates the whole space 𝔽2dR.Property 5.
Let{H0,H1,H2,…HK} be a nonredundant  R-recoverable reduction scheme with  R≤K. Obfuscating group  M=H0 together with reduction scheme  {H1,H2,…HK} is a secret-sharing scheme that achieves perfect secrecy.Proof.
Since scheme{H0,H1,…HK} is not redundant, then we have, by definition, H0(Hj1∩⋯∩HjL)=G as soon as Hj1∩⋯∩HjL≠E.According to Property5, constructing secret-sharing schemes that achieve perfect secrecy is simple as soon as one has a nonredundant scheme with enough subgroups: just use one of the subgroups as the obfuscating group.


## 4. Examples of Alternative Reduction Schemes

In order to show the flexibility and the generality of the presented theory, in this section, we present some schemes that are not expressible as schemes based on vector spaces over finite fields. With respect to the Vandermonde scheme, the schemes presented here have the characteristic that they do not require arithmetic in finite fields but only ordinary integer arithmetic, and this, depending on the applicative context, could be interesting from a complexity point of view. Moreover, the redundancy of the schemes presented here can be easily adapted to the specific application requirements: low redundancy (or none at all) if efficiency is required and more redundancy if error protection is needed.


### 4.1. CRT-Based Reduction Scheme

Letp1,p2,…,pL be mutually prime numbers (i.e., the greatest common divisor of pi and pj≠pi is 1), and let N=p1⋯pL. We will consider the group ℤ/Nℤof the integers modulo N. Every subgroup of ℤ/Nℤ has the form Mℤ/Nℤ, where M divides N. The reduction of x=u+Nℤ∈ℤ/Nℤ with subgroup Mℤ/Nℤ is (umodM)+Mℤ/Nℤ. Note that since M divides N, coset (umodM)+Mℤ/Nℤ does not depend on the representative chosen for u+Nℤ.Let us consider, as an example, the caseN=210. In this case, the content symbols are integers in the range 0⋯209, the reduction with subgroup Mℤ/210ℤ is the usual reduction modulo M, and Property 1 reduces itself to the Chinese remainder theorem. A reduction scheme based on the group ℤ/210ℤ is uniquely specified by giving a set of subgroups of ℤ/210ℤ.Figure2 shows the lattice of the subgroups of ℤ/210ℤ. Subgroup Mℤ/210ℤ is labeled with M in Figure 2; therefore, the bottom node of Figure 2 represents the trivial group E≃210ℤ/210ℤ, while the top node represents the content alphabet G=ℤ/210ℤ. By choosing the nodes marked with a star, one obtains a reduction scheme with no redundancy that enjoys the 4-reconstruction (tight) property, while choosing the node marked with a circle, one obtains a scheme that enjoys a 3-reconstruction property but not tight, since in some cases, only two reduced versions suffice. Moreover, the scheme associated with the circles is redundant, since the least upper bound of two nodes marked with circles is not the top node.Figure 2
Lattice of the subgroups ofℤ/210ℤ. A node labeled with M represents group Mℤ/210ℤ.


### 4.2. Point Lattice Reduction Schemes

LetM∈ℤD×D be a square matrix with integer entries with detM≠0. The point lattice of base M is the set MℤD⊂ℝD obtained by taking integer linear combinations of the columns of M; that is,(22)MZD≔{Mn,n∈ZD}.
(Typically, MℤD is called simply lattice; here we use the term point lattice in order to avoid confusion with the lattices introduced in Appendix B.) A point lattice is clearly a subgroup of ℤD. It is known [11, 15] that |ℤD/MℤD|=detM. Since ℤD/MℤD is finite, it is a suitable group for building reduction schemes.Consider, for example, the case whereM=diag(4,4). It is easy to see that each class of ℤ2/Mℤ2 can be uniquely identified by its representative belonging to the set {0,…3}×{0,…,3}. Such a representative can be encoded by using four bits: two bits per component. Note that each subgroup of ℤ2/Mℤ2 has the form Nℤ2/Mℤ2, where N is an integer matrix such that N-1M has integer entries [15]. By exploiting the Hermite normal form theorem, it is possible to show that N can be supposed without loss of generality in lower triangular form. If n1 and n2 are the diagonal elements of N, it is easy to check that every class of [ℤ2/Mℤ2]/[Nℤ2/Mℤ2] can be uniquely identified by its representative belonging to the set {0,…,n1-1}×{0,…,n2-1}. Since detN=n1n2 must divide detM=16, we are granted that both n1 and n2 must be powers of two, making the binary representation of the representative trivial.Figure3 shows the lattice graph of the subgroups of ℤ2/Mℤ2. (The lattice graph of Figure 3 can be obtained by using the algorithm in [16].) As for the case of Figure 2, each node in Figure 3 is labeled with the corresponding N matrix; therefore, the top node corresponds to the content alphabet ℤ2/Mℤ2, while the bottom node corresponds to the trivial group E≃Mℤ2/Mℤ2.Figure 3
Lattice of the subgroups ofℤ2/4ℤ2. A node labeled with M represents group Mℤ2/4ℤ2.Several choices for reduction schemes are possible.(1) Use the two subgroups marked with full circles and the one marked with an empty circle. This gives a 2-tight scheme (the first common descendant of each pair of nodes is the node corresponding toE≃Mℤ2/Mℤ2) without redundancy (the first common ancestor of each pair of nodes is the node corresponding to G=ℤ2/Mℤ2).If[x,y]t, x,y∈{0,…,3} represents the symbol to be reduced, it is easy to show that the reduction with respect to the subgroups shown in Figure 3 can be done as follows:(23)[xy]mod⁡[14]=[0y],[xy]mod⁡[114]=[0(y-x)mod⁡4],[xy]mod⁡[41]=[x0].
Note that the result of each reduction in (23) requires two bits to be encoded, and this is coherent with the fact that this scheme is 2-tight and non redundant.Note that reductions (23) do not require arithmetic in a Galois field but only normal integer arithmetic. This can be interesting from an implementation point of view.(2) If the two subgroups marked with full circles and the one marked with the star are chosen, one obtains a scheme that is not 2-tight anymore, since, for example, node 2 and node 6 have as common descendant node 13. The scheme, however, is not redundant, since every pair of nodes has as common ancestor node 1.(3) If the two subgroups marked with full circles and the ones marked with a triangle are chosen (nodes 6, 11, and 12) one obtains a redundant scheme, since nodes 6 and 12 have as common ancestor node 9.Remark 5.
It is worth observing that the scheme proposed here isnot to be confused with lattice-based error correction codes proposed in the literature (see [17] for an introduction). Generally speaking, lattice-based error correction schemes exploits the “metric” properties of lattices that derive from the fact that a lattice is subset of ℝN. In our case, we use the lattice only as an abstract group and not as the subset of a metric space. This distinction can be made clearer by observing that if one in an error correction scheme replaces the lattice with another one, almost surely the properties of the error correction scheme will change; in our scheme, one can replace the lattice with any other isomorphic group, and the overall properties of the scheme will not change.


## 4.1. CRT-Based Reduction Scheme

Letp1,p2,…,pL be mutually prime numbers (i.e., the greatest common divisor of pi and pj≠pi is 1), and let N=p1⋯pL. We will consider the group ℤ/Nℤof the integers modulo N. Every subgroup of ℤ/Nℤ has the form Mℤ/Nℤ, where M divides N. The reduction of x=u+Nℤ∈ℤ/Nℤ with subgroup Mℤ/Nℤ is (umodM)+Mℤ/Nℤ. Note that since M divides N, coset (umodM)+Mℤ/Nℤ does not depend on the representative chosen for u+Nℤ.Let us consider, as an example, the caseN=210. In this case, the content symbols are integers in the range 0⋯209, the reduction with subgroup Mℤ/210ℤ is the usual reduction modulo M, and Property 1 reduces itself to the Chinese remainder theorem. A reduction scheme based on the group ℤ/210ℤ is uniquely specified by giving a set of subgroups of ℤ/210ℤ.Figure2 shows the lattice of the subgroups of ℤ/210ℤ. Subgroup Mℤ/210ℤ is labeled with M in Figure 2; therefore, the bottom node of Figure 2 represents the trivial group E≃210ℤ/210ℤ, while the top node represents the content alphabet G=ℤ/210ℤ. By choosing the nodes marked with a star, one obtains a reduction scheme with no redundancy that enjoys the 4-reconstruction (tight) property, while choosing the node marked with a circle, one obtains a scheme that enjoys a 3-reconstruction property but not tight, since in some cases, only two reduced versions suffice. Moreover, the scheme associated with the circles is redundant, since the least upper bound of two nodes marked with circles is not the top node.Figure 2
Lattice of the subgroups ofℤ/210ℤ. A node labeled with M represents group Mℤ/210ℤ.


## 4.2. Point Lattice Reduction Schemes

LetM∈ℤD×D be a square matrix with integer entries with detM≠0. The point lattice of base M is the set MℤD⊂ℝD obtained by taking integer linear combinations of the columns of M; that is,(22)MZD≔{Mn,n∈ZD}.
(Typically, MℤD is called simply lattice; here we use the term point lattice in order to avoid confusion with the lattices introduced in Appendix B.) A point lattice is clearly a subgroup of ℤD. It is known [11, 15] that |ℤD/MℤD|=detM. Since ℤD/MℤD is finite, it is a suitable group for building reduction schemes.Consider, for example, the case whereM=diag(4,4). It is easy to see that each class of ℤ2/Mℤ2 can be uniquely identified by its representative belonging to the set {0,…3}×{0,…,3}. Such a representative can be encoded by using four bits: two bits per component. Note that each subgroup of ℤ2/Mℤ2 has the form Nℤ2/Mℤ2, where N is an integer matrix such that N-1M has integer entries [15]. By exploiting the Hermite normal form theorem, it is possible to show that N can be supposed without loss of generality in lower triangular form. If n1 and n2 are the diagonal elements of N, it is easy to check that every class of [ℤ2/Mℤ2]/[Nℤ2/Mℤ2] can be uniquely identified by its representative belonging to the set {0,…,n1-1}×{0,…,n2-1}. Since detN=n1n2 must divide detM=16, we are granted that both n1 and n2 must be powers of two, making the binary representation of the representative trivial.Figure3 shows the lattice graph of the subgroups of ℤ2/Mℤ2. (The lattice graph of Figure 3 can be obtained by using the algorithm in [16].) As for the case of Figure 2, each node in Figure 3 is labeled with the corresponding N matrix; therefore, the top node corresponds to the content alphabet ℤ2/Mℤ2, while the bottom node corresponds to the trivial group E≃Mℤ2/Mℤ2.Figure 3
Lattice of the subgroups ofℤ2/4ℤ2. A node labeled with M represents group Mℤ2/4ℤ2.Several choices for reduction schemes are possible.(1) Use the two subgroups marked with full circles and the one marked with an empty circle. This gives a 2-tight scheme (the first common descendant of each pair of nodes is the node corresponding toE≃Mℤ2/Mℤ2) without redundancy (the first common ancestor of each pair of nodes is the node corresponding to G=ℤ2/Mℤ2).If[x,y]t, x,y∈{0,…,3} represents the symbol to be reduced, it is easy to show that the reduction with respect to the subgroups shown in Figure 3 can be done as follows:(23)[xy]mod⁡[14]=[0y],[xy]mod⁡[114]=[0(y-x)mod⁡4],[xy]mod⁡[41]=[x0].
Note that the result of each reduction in (23) requires two bits to be encoded, and this is coherent with the fact that this scheme is 2-tight and non redundant.Note that reductions (23) do not require arithmetic in a Galois field but only normal integer arithmetic. This can be interesting from an implementation point of view.(2) If the two subgroups marked with full circles and the one marked with the star are chosen, one obtains a scheme that is not 2-tight anymore, since, for example, node 2 and node 6 have as common descendant node 13. The scheme, however, is not redundant, since every pair of nodes has as common ancestor node 1.(3) If the two subgroups marked with full circles and the ones marked with a triangle are chosen (nodes 6, 11, and 12) one obtains a redundant scheme, since nodes 6 and 12 have as common ancestor node 9.Remark 5.
It is worth observing that the scheme proposed here isnot to be confused with lattice-based error correction codes proposed in the literature (see [17] for an introduction). Generally speaking, lattice-based error correction schemes exploits the “metric” properties of lattices that derive from the fact that a lattice is subset of ℝN. In our case, we use the lattice only as an abstract group and not as the subset of a metric space. This distinction can be made clearer by observing that if one in an error correction scheme replaces the lattice with another one, almost surely the properties of the error correction scheme will change; in our scheme, one can replace the lattice with any other isomorphic group, and the overall properties of the scheme will not change.


## 5. Conclusions

This paper proposed a general framework for reduction schemes based on group theory. The new framework, while containing the vector space approach as a special case, allows to design schemes that cannot be modeled as linear codes. The properties of the GBRS have been analyzed, and it has also been shown how a GBRS can be used to prevent stream poisoning and how GBRS can be converted into a secret-sharing scheme achieving perfect secrecy. Examples of group-based schemes that cannot be described in the vector space framework have also been shown.



---

*Source: 898254-2011-09-08.xml*