Coding and Cryptography

URL study guide

https://studiegids.vu.nl/en/courses/2024-2025/X_405041

Course Objective

Upon completion of this course:The student knows basic coding theory (rate, weight, distance, distance of a code, bounds, error correcting/detecting, linear codes including generating matrix, parity check matrix, and how to use the latter to find the distance) and can solve problems about and with those in explicit situations.The student knows cyclic linear codes over the field with 2 elements (cyclic linear code generated by an element, generator polynomials, how to find them using idempotents, and the relation with divisors of 1+xⁿ) and can solve problems about them in explicit situations.The student knows the notion of irreducible polynomial, how to work modulo a polynomial (including the use of a table), the notion of minimal polynomial, and can calculate with those in explicit situations.The student knows cyclic Hamming codes and 2-error correcting BCH-codes over the field with 2 elements and can apply the decoding algorithms for those.The student knows Reed-Solomon codes of a given design distance and can apply two decoding algorithms to those in explicit situations.The student knows some basic cryptography (including the Miller-Rabin probabilistic prime test, RSA and ElGamal) and can apply those in explicit situations. Each of these is part of "Knowledge and understanding" as well as "Applying knowledge and understanding".

Course Content

This course provides a thorough introduction to the theory of error-correcting codes, and also, as a small part of it, treats the algebraic background of some protocols in cryptography. It is aimed especially at students of Computer Science. For error-correcting codes, we shall include cyclic codes, BCH codes, Reed-Solomon codes, and burst error correction. These are used in the error-correcting codes underlying, for example, CD-ROM, audio CD, and QR codes. For the small part on cryptography we discuss some modern public-key cryptography (e.g., RSA, ElGamal, DSA), which form part of the protocol underlying HTTPS.

Teaching Methods

Lectures (four hours per week during the seven weeks of the period) and exercise classes (two hours per week during the seven weeks of the period).

Method of Assessment

Written exam and a compulsory assignment. The written exam will count for 80% of the grade, the assignment for 20%. If not both the written exam and the homework are at least 55% each, then the maximum score will be 54% (which constitutes a fail). There are resits for both the exam and the assignment, governed by the same rules, and within the same academic year, the exam and assignment can be passed at either attempt.

Literature

Baylis, J. (2001). Coding theory and cryptography
- the essentials (2nd ed.), by D.R. Hankerson, D.G. Hoffman, D.A. Leonard, C.C. Lindner, K.T. Phelps, C.A. Rodger and J.R. Wall.

Target Audience

MSc Computer ScienceMSc Computer SecurityMSc Mathematics

Recommended background knowledge

Some knowledge of linear algebra (vectors, matrices, nullspaces, linear (in)dependence, basis, dimension, inner/dot product, some determinants), on the integers modulo n, and of polynomials. Although these will be reviewed, experience shows that the course is difficult to follow without having seen this material before. This is particularly true for the background on linear algebra, as it plays a major role in the set-up and study of linear codes and many of their properties are interpreted using it.