Simultaneous Encryption using Linear Block Channel Coding Part2

Posted by CRYPTOcrat | Encryption | Wednesday 29 October 2008 7:24 am

In continuation from Part 1 of this article here.

Linear Block Codes: Generator Matrix and Systematic Codes

LBC use the concept of adding redundancy in the form of Parity bits so as to give information about error correction.

A vector matrix equation is:

U = mG (1)

(2)

To form a systematic code the generator matrix G can be modified in terms of sub matrices P and Ik as follows:

U = mG = m[P|Ik ]…(3)

(4)

Error Detection and the Parity-Check Matrix

HT is an n × (n - k) matrix (whose rows are the columns of H). To fulfill the orthogonality requirements of a systematic code, the H matrix can be written as H = [In-k | PT ], where In-k represents an (n - k) × (n - k) identity sub matrix and P represents the parity sub matrix defined. Since by this definition of H, we see that GHT = 0, and since each U is a linear combination of the rows of G, then any vector r is a code word generated by the matrix G, if and only if

rHT = 0…. (5)

Equation (5) is the basis for verifying whether a received vector r is a valid code word.

Towards Error Correction: Syndrome Testing

Following (5), we define a syndrome vector S of r as

S = rHT. …(6)

Error Correction:

The Syndrome actually relates us to the actual Error as follows:

S = rHT = (Ui + ej ) HT = UiHT + ejHT…(7).

From this, the error pattern can be decided.

The Scheme for Simultaneous Channel Coding and Encryption:

Key Matrix:

We use a Key Matrix: L of dimensions (n by n)

The Key Matrix is a special a Square Matrix for which Inverse exists.

Hence, find L-1 such that [L][ L-1]= [I]…. (8 )

We call the matrix L-1 as the Multiplicative Inverse for the *[L] operation.

Encrypted Code-Word Matrix U”:

The Code-word matrix U is converted into the encrypted matrix U” by

[U]*[L]= [U''](9)

The received vetor will have added error as given below:

The source codes used for communication will all be from the [U''] matrix which cannot be decoded until the n*n matrx [L] is known.

Z= U” + e … (10)

For decoding the code-word to the right vector, we use the multiplicative inverse at the receiving end.

Hence,

S = rHT = (Ui*L+ ej)([L -1HT ) ...(11)

=  (Ui* L* L-1 *HT )+( ejHT L-1)

= (Ui*HT )+( ejHT L-1)

S = ( ejHT L-1) ...(12)

Hence we modify the syndrome table from ejHT to ( ejHT L-1).

With this minor change the whole code word is retrieved along with error pattern.

<!– /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-parent:”"; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:”Times New Roman”; mso-fareast-font-family:”Times New Roman”;} @page Section1 {size:8.5in 11.0in; margin:1.0in 1.25in 1.0in 1.25in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.Section1 {page:Section1;} –>

Example: (6, 3) Linear Block Code

Table 2 describes a code word-to-message assignment for a (6, 3) code, (Sklar [3])

The Generator Matrix for (6,3) code:

[G]=

(13)

The Message Matrix [M] for (6,3) code:

[M]=

(14)

The Key Matrix for this (6,3)code:

[L]=

(15)

Calculating : [U]=[M][G]:

[U]=

(16)

Calculating the New Encrypted Code Word Matrix U”

[U''] = [U]*[L] =

(17)

Note that [U''] is quite different from [U], and cannot be traced back unless one has key matrix [L].

Retrieval of [U] from [U'']

Getting [U]= [U'']*[L -1] =

(18)

The rest of decoding can now be done by using the standard decoder and the Syndromes may as well be interpreted for error patterns with minor changes as explained in the expression (12).

Conclusions:

Use of Channel Coding for Simultaneous Encryption purpose is a better choice as compared to the use of Source coding because of the Resdundancy increase found in Channel Coding and the possibilities for having higher key lengths for encryption.

We here present a novel way to simultaneously encrypt the message while channel coding is performed.The method proposed does not alter the noprmal performance of the Channel coding by linear block codes, and infuses encryption as an added advantage. The method also does not impose any extra overheads as the matrix G” can be pre-calculated using the multiplication [G]*[L]. Similarly at the receiving end, the matrix HT ” can be calculated beforehand by [HT]*[ L -1].

It shall be noted that the method does not make use of the standard approach of exploiting the freedom in coding method. It makes use of the concept of multiplicative inverse for removing encryption layer which is imposed by a prior multiplication.

References

[1] Chung-E Wang, “Cryptography in Data Compression“, CodeBreakers

Journal Vol. 2, No. 3 (2005).

[2] Chung-E Wang, “Simultaneous Data Compression and Encryption“,

Security and Management 2003: 558-563.

[3] Bernard Sklar, “The ABCs of Linear Block Codes”, IEEE Signal

Processing Magazien, July 2004.

[4] John G. Proakis, “Digital Communication“, Mc-Graw Hill Companies,

(2007)

[5] B. Sklar, Digital Communications: Fundamentals and Applications, 2nd

ed.Englewood Cliffs, NJ: Prentice-Hall Inc., 2001.

[6] T. Kasami, Klove, and S. Lin, “Linear block codes for error

detection,”IEEE Trans. Inform. Theory, vol. IT-29, pp. 131-136, Jan.

1983.

[7] W.W. Peterson and E.J. Weldon, Error Correcting Codes. Cambridge,

MA:MIT Press, 1972.

[8] Online Matrix Multiplier: http://wims.unice.fr/wims/wims.cgi

Simultaneous Encryption using Linear Block Channel Coding Part1

Posted by CRYPTOcrat | Encryption | Sunday 5 October 2008 6:38 pm

This article is authored by Rohit Pandharkar a fellow CRYPTOcrat.  Rohit is currently pursuing his under graduate studies at College of Engineering Pune. He has great interests in Cryptography, Mathematics and at this early stage has already published couple of research papers related to Cryptography.

You can find more information about Rohit on his LI Profile.

Introduction

Channel coding is an error-control method used for providing robust data transmission through imperfect channels by adding redundancy to the data. Two vital classes of such coding techniques are: block and convolutional. In this article, we will be focusing on the Linear Block Coding and its use for encryption in this work.

The attempts at simultaneous source coding and encryption mainly involved exploitation of the freedom involved in the compression algorithms. Chung-E Wang [1], [2] has worked extensively in the area of Cryptography in data Compression, and has delved into the possibilities of exploiting the freedom in the source coding algorithmic for the sake of encryption.

Need to use Channel Coding for Encryption:

We opt for channel coding as a better point of infusing encryption as compared to the source coding because of the following reasons:

Limitations of infusing secrecy when simultaneously compressing.

A) Limitations due to reduction in Redundancy

The Source Coding Algorithms by default decrease the redundancy in the original dta, whereas channel coding techniques increase the redundancy. The more the redundancy, the more the secrecy can be infused according to Shannon.Hence, Channel Coding is a better choice for simultaneous encryption.

B) Limitation on the length of the key

Length of the key is an important factor in determining the strength of encryption. Longer lengths of keys help preventing the brute force and chosen plain text attacks.

In Huffman coding:,the limit on using joint compression and encryption approach is that, the key length cannot be more than the number of parent nodes present in the tree. And hence maximum key length is dependent on Message characteristics and prefix coding scenario. This restraint is related to

1. Number of symbols

2. Probability distribution of the symbols

However, as shown in the further work, the encryption using channel coding can have a key matrix of n*n dimensions, and hence has better key length strength.

Combining ‘Channel’ Coding and Encryption without using freedom:

Considering the relations established by Shannon between source coding and encryption, and looking at the possibility of exploiting the freedom in the source coding algorithms, we look for alternative possibilities for simultaneous channel coding and encryption without using the freedom within the algorithms.

In this article, we present a Matrix-based method for simultaneous Encryption and channel coding using Linear Block Codes. The method presented is different from the previous attempts by others so far for simultaneous coding and encryption in that it does not use the freedom or choice involved in the coding algorithms. It essentially uses a key matrix to add an encryption layer on the code-word matrix. The original code-word matrix is recovered by nullifying the encryption layer at the receiving end. This needs special Key Matrix design. The design considerations for this key matrix are elaborated and the encryption procedure is explained with the help of an example for the (6,3) Linear Block Code.

To be continued in the next part.

soccerine Wordpress Theme