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

No Comments

Please note the views expressed in the comments below are that of the commenter and the owners of this website may not agree with the views expressed.

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

soccerine Wordpress Theme