Secure information flow for IoT applications

ry storage as well as the decoding
complexity, a parity-check matrix with small number of
rows is preferred.
 Given any linear code and any given maximum num-
ber of correctable erasures, Abdel-Ghaffar and Weber
introduced separating matrices yielding parity-check
equations that do not check any of the erased symbols
and which are sufficient to characterize all punctured
codes corresponding to this maximum number of era- Figure 4. An l-separating matrix.
sures [7]. This allows for the separation of erasures
from errors to facilitate decoding. However, their pro-
posal yields separating matrices which typically have enough parity-check equations that do not check
too many redundant rows. The following part of this any erased symbols, and are sufficient to charac-
paper discusses an improved method to construct such terize the punctured code. It means that the punc-
separating matrices, applying covering design, with a tured code, which is formed by deleting erased
smaller number of rows. symbols, can be corrected errors by a sub-matrix
 of H.
 • In case l ≤ min{d, n − k} − 1, H has no stopping
3 How to Build an L-separating Matrix set of size l or less. For any pattern of l or fewer
 erasures, not only are there enough parity-check
3.1 Set Separation
 equations that do not check any of the erased
 Let H = (hi,j) of rank n − k be an (r × n) parity-check symbols characterize the punctured code, but also
matrix of C, r ≥ n − k. Let S be a subset of {1, 2, . . . , n} there is a parity-check equation that checks exactly
 T
and T be a subset of {1, 2, . . . , r}, define HS = (hi,j) one of the erased symbols. It means that after
with i ∈ T and j ∈ S, be a |T| × |S| submatrix of H. For all errors have been corrected, erasures can be
the code C with the length n, define CS = {cS : c ∈ C} recovered by the iterative decoding procedure.
be the punctured code consisting of all codewords of
C in which the symbols in positions indexed by S, S =
 3.2 Separating Matrix
{1, 2, ..., n}\ S are deleted. Clearly, CS is a linear code
 0   0 0
over GF(q) of length n = S, dimension k ≤ k, and Let H be a full rank parity-check matrix, Si ⊆
 0   n
 ≤ − = { ≤ ≤ {1, 2, ..., n}, in which i = 1, 2, . . . , ( l ), be distinct subsets
Hamming distance d d S. Let Se i : 1 i 0
 S of {1, 2, ..., n} of size l, For each i, it is trivial that H
r, h = 0, ∀j ∈ S}, define H(S) = He. Si
 i,j S has rank l (l ≤ min{d, n − k} − 1). By elementary row
Definition 1 ([7]). A parity-check matrix H of an [n, k, d] operations on H0, we can obtain an (n − k) × n matrix
 0 n
linear code C separates a set S of size |S| ≤ d − 1 iff H(S) Hi, for each i = 1, 2, ..., ( l ), of rank n − k, such that its
has rank n − k − |S|. last n − k − l rows have zeros in positions indexed by Si,
 as given in Figure 3.
Theorem 1 ([7]). A parity-check matrix H of an [n, k, d]
 Let H be a matrix which rows is the union of sets
linear code C separates a set S of size |S| ≤ d − 1 iff H(S) I
 of the last n − k − l rows in H0, for i = 1, 2, ..., (n). H is
has rank n − k − |S|. i l I
 an l-separating matrix of the code C, and it has at most
 n
Definition 2 ([7]). If H separates all sets S of size l for a ( l )(n − k − l) rows [7], as illustrated in Figure 4.
fixed l ≤ min{d, n − k}, it is l-separating.
 If H is an l-separating parity-check matrix of the 3.3 A More Efficient Separating Matrix
code C, based on H, we can construct a parity-check In this section, we propose a method that can con-
matrix for any code punctured up to a fixed number l struct an l-separating matrix with a smaller number
of symbols. H has two features: of rows. This method implements the idea of covering
 • H can separate erasures from errors, since H has design [13, 14]. Basically, given 1 ≤ t ≤ u ≤ v, a (v, u, t)
T. M. Ngo & V. N-D-Nhat: Secure Information Flow for IoT Applications 27
 0
 union of the last n − k − l rows in Hj, j = 1, 2, ..., |B|, and
 0 n
 the rows l + 1, l + 2, ..., b of Hi , i = 1, 2, . . . , ( l ), is an l-
 separating parity-check matrix of C. Let B(n, b, l) denote
 the minimum size of B, i.e., B(n, b, l) = min |B|. This
 n
 matrix has at most (n − k − b)B(n, b, l) + ( l )(b − l) rows.
 It is obvious to see that the upper bound on number of
 rows in this part is strictly smaller than in the previous
 one. In case b = l, two approaches are the same. For a
 given l, we can choose an appropriate b to achieve the
 best result.
 Figure 5. Row separation - Step 1.
 4 Covering Design
 Consider a (v, u, t) covering design, where 1≤ t ≤ u ≤ v.
 Example 1.
 8
 Given that v = 8, u = 3, t = 2. There are (2) = 28 sub-
 8
 sets of 2-elements, and (3) = 56 subsets of 3-elements
 of V = {1, 2, ..., 8}. However, we only need at most 21
 subsets of 3-elements, i.e., {1, 2, 3}, {1, 2, 4}, {1, 2, 5},
 {1, 2, 6}, {1, 2, 7}, {1, 2, 8}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6},
 Figure 6. Row separation - Step 2.
 {1, 3, 7}, {1, 3, 8}, {1, 4, 5}, {1, 4, 6}, {1, 4, 7}, {1, 4, 8},
 {1, 5, 6}, {1, 5, 7}, {1, 5, 8}, {1, 6, 7}, {1, 6, 8}, {1, 7, 8}},
 to form all 28 subsets of 2-elements. For example, based
 on the subset {1, 2, 3}, we can form {1, 2}, {2, 3}, {1, 3}.
 Using 21 subsets of size 3 mentioned above, we can
 construct all 28 subsets of size 2.
 The covering design problem has been investigated
 since many years ago. However, until now, there is
 no general optimal solution for all triples (v, u, t). In
 this section, we propose a covering design valid for all
 triples (v, u, t). This design is not optimal but it can give
 Figure 7. A more efficient l-separating matrix. a general solution for the problem.
covering design is a collection of u-element subsets of 4.1 Approach 1
V = {1, 2, ..., v}, called blocks, such that each t-element v−(u−t)
 Firstly, we show that with at most ( t ) subsets
subset of V is contained in at least one block, e.g., {1, 2} v
 of size u, we can form all (t) subsets of size t.
is contained in {1, 2, 3}. 1) Take the first u − t elements, i.e., {1, 2, ..., u − t},
 For our specific situation, consider an (n, b, l) cover- out of V = {1, 2, ..., v}.
ing design. Let B = {Bi} be a set of b-element subsets, 2) The rest of the set is {u − t + 1, u − t + 2, ..., v −
1 ≤ l ≤ b ≤ min{d, n − k} − 1, such that every l-element 1, v}. Based on these elements, form all subsets of
subset Si is contained in at least one member of B. v−(u−t)
 n size t. The number of subsets is ( t ).
Assign to each Si, i = 1, 2..., ( l ), an element Bj of B
 0 3) Put the first u − t elements into each subset of size
such that Si is contained in Bj. H has rank b. For any v−(u−t)
 Bj t to have subsets of size u. With these ( )
 0 t
Bj, by elementary row operations on H , we can obtain subsets of size u, it is easy to see that we can form
an (n − k) × n-matrix of rank n − k such that its last v−(u−t)
 all ( t ) subsets of size t.
n − k − b rows have zeros in positions indexed by Bj.
After arranging columns, we obtain a matrix H1 with
 j 4.2 Approach 2
the following format (Step 1), given in Figure 5.
 Consider the set Si assigned to Bj, by further elemen- By modifying Approach 1, we show that some u-
 1 element subsets can be merged to reduce |B|.
tary row operations, Hj can be changed into a matrix
such that rows l + 1, l + 2, ..., b have zeros in positions 1) Take the first u − t elements, i.e., {1, 2, ..., u − t},
indexed by Si, and rows b + 1, b + 2, ..., n − k have zeros out of V = {1, 2, ..., v}.
in positions indexed by Bj. After column arrangement, 2) The rest of the set is {u − t + 1, u − t + 2, ..., v −
we obtain a matrix with the following format (Step 2), 1, v}. Based on these elements, form all subsets of
given in Figure 6. size t and arrange them into columns based on
 Following this method, if Si and Si0 belong to the the following rules:
 0 0 •
same Bj, the last n − k − b rows in Hi and Hi0 are the Elements in each subset are arranged in as-
same. Figure 7 shows that the matrix which rows is the cending order, e.g., {1, 2, 3}.
28 REV Journal on Electronics and Communications, Vol. 9, No. 3–4, July–December, 2019
 • Subsets are arranged into columns. Subsets
 are in one column iff their first t − 1 elements
 are the same (except the special column men-
 tioned below). Hence, subsets in one column
 are different from each other only in the last
 element. The subset with the smaller last ele-
 ment will be listed above.
 • Special column: In case t ≥ 2, we arrange all
 subsets containing both element v − 1, v in a
 column and name it special column. It is easy
 v−(u−t)−2
 to see that there are ( t−2 ) subsets in this
 column.
 3) Put the first u − t elements into each subset of size
 t to have subsets of size u.
 4) If the number of subsets in the longest column is
 greater or equal to three and the special column
 exists, we can merge the last two subsets, which
 contain either v − 1 or v, in each column (except
 the special column) into one, i.e., the merged set,
 by this rule
 • Take the union of two subsets, i.e., the size of
 the union subset is u + 1.
 • Eliminate the first element of the union subset,
 i.e., its size is now u.
 We can merge the last two subsets in each column
(except the special column) because: (a) The first u −
 Figure 8. The first three steps of Approach 2.
1 elements in the last two subsets are also in another
subset in the columns. Thus, any subset of size t formed
by using these u − 1 elements can be form by any other
subset in the column; (b) Any subset of size t containing
{1, v − 1} or {1, v} can be formed by subsets in the
special column.
Example 2.
 Given that v = 9, u = 5, t = 4. Following the first
three steps of Approach 2, we get the following result,
as illustrated in Figure 8.
 First, take {1} out of the set. Following Step 2, form
all subsets of size 4, and arrange them into columns.
Put {1} back into each subset of size 4 to have subsets
of size 5. We denote subsets in boxes are subsets which
can be merged.
 The merged step (Step 4): For example, consider the
first column, two subsets in the box are {1, 2, 3, 4, 8}
and {1, 2, 3, 4, 9}. First, take the union of the two, i.e.,
{1, 2, 3, 4, 8, 9}, and then eliminate the first element;
thus, this results in {2, 3, 4, 8, 9}.
 Therefore, Step 4 of Approach 2 gives the following
result. It is easy to see that any subset of size 4 can be
formed by subsets in Figure 9.
 The number of reduced subsets is equal to the num-
ber of subsets that contain the elements v − 1 or v. Thus,
 v−(u−t)−2
the number of reduced subsets is ( − ). Therefore,
 t 1 Figure 9. The last step of Approach 2.
 v−(u−t) − v−(u−t)−2
with at most ( t ) ( t−1 ) subsets of size u,
 v
we can form all (t) subsets of size t.
 more on integrity which can be ensured via the imple-
5 Conclusion mentation of error-correcting codes. Separating parity-
 check matrices are useful for decoding over channels
This paper discusses how to ensure confidentiality and causing both errors and erasures. We propose a way to
integrity for data in IoT systems. The paper focuses build a separating parity-check matrix with a smaller
T. M. Ngo & V. N-D-Nhat: Secure Information Flow for IoT Applications 29
set of rows. This method not only reduces both decod- tions on Information Theory, vol. 52, no. 3, pp. 922–932,
ing complexity and memory storage. Besides, we also 2006.
present a covering design. This design is not optimal [11] J. H. Weber and K. A. S. Abdel-Ghaffar, “Results on
 ( ) parity-check matrices with optimal stopping and/or
but it gives a general solution for all triple v, u, t . dead-end set enumerators,” IEEE Transactions on Infor-
 mation Theory, vol. 54, no. 3, pp. 1368–1374, 2008.
 [12] H. D. Hollmann and L. M. Tolhuizen, “On parity-check
Acknowledgments collections for iterative erasure decoding that correct
 all correctable erasure patterns of a given size,” IEEE
The authors are supported by The University of Danang Transactions on Information Theory, vol. 53, no. 2, pp. 823–
– University of Science and Technology through the 828, 2007.
grant T2019-02-13 and T2019-02-14. [13] J. H. Dinitz and D. R. Stinson, Contemporary design theory:
 A collection of Surveys. John Wiley & Sons, 1992, vol. 26.
 [14] [Online]. Available: 
References
 [1] J. A. Goguen and J. Meseguer, “Security policies and
 security models,” in Proceedings of the IEEE Symposium
 on Security and Privacy. IEEE, 1982, pp. 11–11. Tri Minh Ngo was born in Danang, Vietnam,
 [2] T. M. Ngo and M. Huisman, “Complexity and infor- in 1982. He received a B.E. degree from The
 mation flow analysis for multi-threaded programs,” The University of Danang-University of Science
 European Physical Journal Special Topics, vol. 226, no. 10, and Technology, Danang, Vietnam, in 2005,
 pp. 2375–2392, 2017. and M.E. and Ph.D. degrees from Delft Uni-
 [3] R. M. Roth, Introduction to Coding Theory. Cambridge versity of Technology and The University of
 University Press, 2006. Twente, The Netherlands, in 2009 and 2014, re-
 [4] S. Lin and D. J. Costello, Error control coding. Pearson spectively. He is now a Lecturer at the Faculty
 of Electronic and Telecommunication Engi-
 Education India, 2004. neering, The University of Danang-University
 [5] F. J. Mac Williams and N. J. A. Sloane, The theory of error- of Science and Technology, Danang, Vietnam.
 correcting codes. North-Holland Publishing Company,
 1977, vol. 16.
 [6] S. A. Vanstone and P. C. Van Oorschot, An introduction
 to error correcting codes with applications. Norwell, MA:
 Kluwer, 1989, vol. 71. Vien Nguyen-Duy-Nhat received the B.Eng.
 [7] K. A. Abdel-Ghaffar and J. H. Weber, “Separating era- degree in Electronic Engineering from The
 sures from errors for decoding,” in Proceedings of the University of Danang, University of Science
 International Symposium on Information Theory. IEEE, and Technology, (DUT), Vietnam, in July 1997.
 2008, pp. 215–219. In September 1997, he joined the Department
 [8] J. H. Weber, “Lecture notes: Error-correcting codes,” of Electronics and Telecommunications En-
 Delft University of Technology, 2007. gineering, Danang University of Technology.
 [9] C. Di, D. Proietti, I. E. Telatar, T. J. Richardson, and In 2003, he received the M.Eng. degree in
 R. L. Urbanke, “Finite-length analysis of low-density Electrical Engineering from Ho Chi Minh City
 University of Technology (HCMUT), Vietnam.
 parity-check codes on the binary erasure channel,” IEEE And his Ph.D. degree from The University
 Transactions on Information theory, vol. 48, no. 6, pp. 1570– of Danang in 2017. His current research interests include next-
 1579, 2002. generation wireless communications, wireless system design and
[10] M. Schwartz and A. Vardy, “On the stopping distance optimization, Internet of Things.
 and the stopping redundancy of codes,” IEEE Transac-