Coding and Cryptography

2019-2020

Course Objective

* The student knows basic coding theory (rate, weight, distance,
distance of a code, bounds, error correcting/detecting, linear codes
including parity generating matrix and 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^n)
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 students 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 students knows Reed-Solomon codes of a given design distance and
can apply two decoding algorithms to those in explicit situations.
* The student knows some basics cryptography (including the Miller-Rabin
probabilistic prime test, RSA and ElGamal) and can apply those in
explicit situations.

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), organized in two blocks of three hours (two hours of lectures,
one hour of exercise class).

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.

Literature

We shall work from "Coding theory and cryptography, the essentials" by
Hankerson, Hoffman, Leonard, Lindner, Phelps, Rodger and Wall (second
edition, revised and expanded).

Target Audience

XM_CS 1, XM_PDCS 1, XM_MAT_B 1, XM_MAT_E 1, XM_MAT_T 1, XM_MAT_S 1,
XM_MAT_ADS 1, XM_MAT_AG 1

Recommended background knowledge

Some knowledge on linear algebra (vectors, matrices, nullspaces, linear
(in)dependence, basis, dimension, inner/dot product, some determinants),
on the integers modulo n, and on 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.

General Information

Course Code X_405041
Credits 6 EC
Period P4
Course Level 400
Language of Tuition English
Faculty Faculty of Science
Course Coordinator prof. dr. R.M.H. de Jeu
Examiner prof. dr. R.M.H. de Jeu
Teaching Staff prof. dr. R.M.H. de Jeu

Practical Information

You need to register for this course yourself

Last-minute registration is available for this course.

Teaching Methods Lecture
Target audiences

This course is also available as: