The MSc Programme and the PhD
Programme in Information Theory,
Coding and Cryptography (ITCC)

Dr Khumbo Kumwenda is the Coordinator of these ITCC
Programmes .  

Email:
<Dr Khumbo Kumwenda <khumbo@aims.ac.za>;>

PhD in Coding Theory at Mzuni.  
Check it out at:  
PhD in ITCC Programme

The MSc in Information Theory,
Coding and Cryptography (ITCC)
From 2006 to 2013 thirty two students have graduated from the
programme.  Of these fourteen have continued in academia and are
lecturers, six are pursuing PhD studies, two are employed as
engineers.   Eight more students are due to graduate in November
2010.  At present there are ten students on the programme.

Graduates who have progressed
to PhD Studies in Coding Theory:

  1. Dr Khumbo Kumwenda graduated in 2011 with a PhD in Coding
    Theory from the University of the Western Cape in South Africa
  2. Dr Ezekiel Kachisa graduated with a PhD from Dublin City
    University in Ireland in 2011
  3. Michael Zimba is doing his PhD at the College of Computer and
    Communication, Hunan University, China.
  4. Mrs Mwai Nyirenda-Kayuni is pursuing  PhD studies in
    Cryptography in the UK.
  5. Mr Dalison Nyirenda is pursuing PhD studies in South Africa.


International Input:
1) Dr Chiara Macolla and Dr Emanuele Bellini (University of Trento,
Italy) spent two months during 2013 on MZUNI campus giving input to
the programme.
2) Since the programme began in 2004 no less than eight international
experts have come to Mzuzu and given courses in Coding Theory.  
Their stay at Mzuzu varied from three months to thirteen months.
3) Prof Eric Mwambene, University of the Western Cape, is acting as an
advisor to the programme.  
4) Prof Ed Schaefer, Santa Clara University, USA, acts as an advisor to
the programme.

Independent Review of this MSc
Check out a review of this MSc at An Independent Review

Preamble:
Information Theory, Coding and Cryptography, which from now on we collectively refer to
as Coding Theory, is a very young branch of mathematics having its origins in the
celebrated 1948 Shannon paper. It is a live and exciting area of research today. The
great advances in all types of electronic communication over the past few years are, in
part, due to the continuing developments in Coding Theory. Coding Theory is right at the
cutting edge of technology. The whole subject is fast becoming an integral part of
mathematics in many universities today as it is now included, as an introductory course,
in even undergraduate mathematics courses.

However, as in many other areas, Africa seems to be lagging behind.  In the 2,169 pages
of the Two Volume 1998 Handbook of Coding Theory there is no contribution from
Africa.  Mzuzu University hopes to change this scenario and make a significant
contribution to Coding Theory

Coding Theory:
Coding Theory is essentially about putting information in codes. There might be several
reasons why information would need to be coded.

  1. One reason is to hide it, or make it inaccessible for unauthorised users. Such
    codes   are the subject of Cryptology. Some cryptographic codes (public key)
    form the basis of security of passwords and PIN numbers, which have become
    very common in E-commerce.
  2. Another reason would be to compress the information in order to reduce the
    amount of space needed to store it. An example of such codes would be the 'zip'
    codes used to compress files on computer hard-disks. This compressing is also
    considered essential for the effective transmission of video signals. All this
    comes under the heading of Data Compression.
  3. A third reason is to increase safety and accuracy in the storage or transfer of
    information. Electronic equipment used to store, transfer and manipulate data is
    prone to errors of various kinds. Such an error will for example cause the
    character ‘1’ to become ‘0’ while being transferred from one place to another,
    consequently causing the information to be misinterpreted. Remember, in digital
    transmission all data is stored as a series of ‘1s’ and ‘0s’. It is therefore desirable
    to have some way of detecting --and if possible, correcting-- such errors. That is
    what Error Correcting Codes are about.

Coding theory is a remarkable example of how Pure Mathematics can be used to solve
practical problems. In former times Pure Mathematics was considered more of an ‘Arts
subject’ rather than a ‘Science subject’ because it was considered abstract (pure) and
not practical. In some quarters a ‘practical application’ was even considered as a
‘tainting or diluting’ of the Art of Pure (Abstract) Mathematics. It was as if ‘Art’ had
nothing to do with ‘practical things’. Coding Theory has blown this myth. Coding Theory is
now recognised as an extraordinary beautiful practical application of Pure
Mathematics.  It is the ‘perfect marriage’ of Abstract Theory and the Practical.

Information Theory:
Information Theory using the mathematical tools of probability and statistics quantifies
what is possible and what is not possible. Part of Shannon’s genius was to prove in 1948
that efficient codes existed long before such codes were discovered. It is in fact only in
the last couple of years that codes were found to meet the bounds given by Shannon.

Career Options:
The various topics in Coding Theory play increasingly important roles in efficient,
reliable, and secure systems for information transmission and storage. Applications
include mobile telephony, high density computer and optical disks, digital audio, DVD,
financial and internet services, video-conferencing, digital television, miniaturization in
electronic devices, ATM cards and other smart cards. Graduates from this course will
be equipped with the theoretical knowledge, which will enable them to become involved
at the highest levels of research and development in these areas. They will also be able
to work in a range of careers within the engineering and computing sectors.

Title of MSc Degree:
MSc in Information Theory, Coding and Cryptography (ITCC).

Course Coordinator:
Dr Kumbo Kumwenda.

Duration of course:
The course will be of two years duration.

Intended Student Intake:
The course can accommodate up to 10 students.

Entry Requirements:
The main requirement for entry is a First Degree with Credit (or Second Class         
Classification) which contains a high level content of mathematics.

Course Summary
The course covers a period of two years and consists of four semesters (Semester 9
and Semester 10 in the first year and Semester 11 and Semester 12 in the second
year).  Semester 9 will be devoted to a Bridging Course which will be offered to all
students.  However those students who have covered comprehensively both Abstract
Algebra and Number Theory and have good grades in their first degree in these areas
may be exempted from this Bridging Course.   Semesters 10 and 11 will be devoted to
four taught modules (two modules per semester).  Semester 12 will be devoted to
project work.  Examination of the taught modules will take place at the end of each
semester on the completion of the module. The project will be submitted by the end of
year two.  If necessary a student may apply to the Coordinator of the Programme for an
extension of the date for the submission of the thesis.  This extension will normally be
three months.   

Course Content
The taught component will comprise seven modules from the following eight modules  
(28h  lectures + 14h tutorials each module)

MSC5900 Computer Programming:

MSC5091 Abstract Algebra:
Basic Algebra of Polynomials and Binomial Expansion, Sets, Vectors and Matrices ,
Permutations and Symmetric Groups,  Groups: Lagrange's Theorem, Euler's Theorem,  
Rings,  Cyclotomic Polynomials,  Primitive roots,  Group Homomorphisms,  Cyclic
Groups,  Cauchy’s Theorem,  Quotient Groups and the Isomorphism Theorems,  Sylow’s
Theorems,  Product Groups and Direct Sum Groups,  Linear Congruences,  Systems of
Linear Congruences,  Ideals in Rings, Principal, Euclidean and Maximal Ideals ,  Finite
Fields,  Vector Spaces,  Linear independence, Bases for Vector Spaces, Subspaces,
Vector Space Isomorphisms and Homomorphisms.  Manipulating some of the above
with Magma Programming.

MSC5092 Number Theory:
Induction and the Well-Ordering Principle,  Some Counting Principles, Permutations and
Combinations,  The Integers,  Divisibility, Bezout’s identity, Linear Diophantine Equations,
Unique Factorization into Primes,  Distribution of the Primes, Algorithm for
Exponentiation, The Group of Units, Primitive Roots, Exponents,  Linear Congruences,  
Systems of Linear Congruences,  Abstract Sun Ze Theorem and the Chinese Remainder
Theorem,   Fermat's Theorem, Primality Tests, Public-Key Ciphers, Implementing some
of the above with C++ Programming.

MSC5103 Error Correcting Codes I
Communicarions Chanels, Error Detection and Correction, Maximum Liklihood Decoding,
Hamming Distance, Nearest Neighbour/Minimum Distance Decoding, Linear Codes,
Distance of a Linear Code, Hamming Weight, Generator Matrix and Parity Check Matrix,
Equivalence of Linear Codes, Encoding with a Linear Code, Decoding of Linear Codes,
Coset Decoding, Nearest Neighbourhood Decoding, Syndrome Decoding, Bounds in
Coding Theory, Lower bounds, Sphere covering bound, Gilbert-Vashamov bound,
Hamming bound and perfect codes, Binary Hamming codes, q-ary Hamming codes,
Golay codes, Singleton bound and MDS codes, Plotkin bound, Greismer bound The Main
Coding Theory Problem, Creating and Manipulating some of the above with Magma
Programming.

MSC5104 Cryptography I
Introduction, vocabulary, terms, history, Number theory review, simple cryptosystems,
modern stream ciphers, finite fields 1, RC4, self-synchronizing stream cipher, one-time
pads, finite fields II, Introduction to Advanced Encryption Standard (AES), Simplied AES,
the real AES, Modes of operation for a block cipher, analysis of simplied AES - (design
rationale, security, efficiency), attacks on block ciphers, repeated squares algorithm,
Running time of algorithms. Public Key cryptography: RSA, use of the Chinese remainder
theorem to speed up RSA decryption, finite field discrete logarithm problem, Diffie-
Hellman key agreement, Lesser used public key cryptosystems - (RSA for message
exchange, ElGamal message exchange, Massey-Omura message exchange), elliptic
curves, elliptic curve discrete logarithm problem, elliptic curve cryptosystems.

MSC6115 Error Correcting Codes II
Non linear codes, Construction of Linear Codes, Propagation Rules, Reed Muller Codes,
Subfield codes, MacWilliams identities, Polynomial Podes, BCH codes, Cyclic Codes,
Quadratic Residue Codes, Generalized Reed Solomon Codes, Alternant Codes, Goppa
Codes, Irreducible Goppa Codes, Goppa Codes defined by a single Field Element,
Equivalence of Goppa Codes, LDPC codes, Convolutional Codes, Automorphism Group of
a Code, Codes used in Public-Key Cryptography.

MSC6116 Goppa Codes
Goppa Codes, Irreducible Goppa Codes, Goppa Codes defined by a single field element,
Affine Sets, Orbits under the Frobenius Automorphism, Equivalence of Goppa Codes,
Upper Bound on the number of Goppa codes, Quasicyclic Goppa codes, Goppa codes in
Cryptography, Use of Magma in Coding Theory.

MSC6117 Cryptography II
Hash functions (MD5) and message authentication codes (MACs), the MD5 hash
algorithm, signatures and authentication, signatures with RSA, ElGamal signature,
Variants of ElGamal signature scheme - ( Schnorr authentication and signature scheme,
Digital Signature Algorithm (DSA), Elliptic curve DSA ), Time-stamping, Kerberos, PKI,
Certificates, PGP, Internet security, Secure Sockets Layer (SSL), IPSec, Key
management, Quantum cryptography, pairing based cryptography for digital signatures,
secret sharing. Cryptanalysis Introduction, types of cryptanalysis, Vigenere cipher, the
Kasiski test, the Friedman test, cryptanaylsis of modern stream ciphers, -(b=p random
bit generator, Linear shift register keystream generator), cryptanalysis of block ciphers
- Linear and differential cryptanalysis of one-round simplified AES, attribute to Pollard,
factoring, Fermat factorization, number bases, continued fraction factoring, H.W.
Lenstra Jr.'s elliptic curve method of factoring, number fields, number field sieve,
solving for DLP in a finite field, the Pollig- Helman algorithm, index calculus algorithm.

MSC6118 Practical Cryptography
Implementation aspects of cryptography.  Efficient algorithms and their implementation
in C++.  A 64-bit crypto library. Implementation of efficient algorithms for Jacobi symbol,
modular exponentiation,  Chinese remainder theorem, prime number generation,
modular inversion and greatest common divisor.  Implementations of some classic
public key schemes (RSA,E1 Gamal, Diffie-Hellman).  A C++ class for finite field
arithmetic.  A C++ class for elliptic curve points.   Implementation of Elliptic Curve
Cryptography.  Counting points on an elliptic curve.  Implementations of some algorithms
for integer factorisation and discrete logarithms. Digital Signature, X509 certificates and
SSL.  DSA and ECDSA. Identity based encryption.  An introduction to pairing-based
cryptography.

Notes:
  • MSC5900 will follow notes left by Prof Scott
  • Both MSC5901 and MSC5902 follow the book ‘Introduction to Abstract Algebra’
    by  Paul Garret and available online at http://www.math.umn.edu/~garrett/
  • MSC5103 follows the first four chapters of  ‘Coding Theory, A first Course’
by San Ling and Chaoping Xing and published by Cambridge University Press 2004
  • MSC5104 follow closely written notes by Prof E. Schaefer
  • MSC5115 follows the last five  chapters of  ‘Coding Theory, A first Course’
by San Ling and Chaoping Xing and published by Cambridge Uni Press 2004.
  • MSC5117 follows closely written notes by Prof E. Schaefer
  • MSC6118 follows notes left by Prof Michael Scott.


Project
A project based on a thorough study of some aspect of the theory with reference to
current applications will form a major part of the course. The project will have to be of a
high standard, preferably containing some research, which is deemed publishable in
some reputable journal.

Division of modules per year:
The Bridging Course Modules MSC 5090, MSC5091 and MSC5092 will be taken during
Semester 9.

Modules MSC 5103 and MSC 5104 will be taken during Semester 10.  These two
modules will be common to all students.

However, there will be two different routes for the second year (Semesters 11 and 12) of
the MSc, namely 1) the Error Correcting Codes route and 2) the Cryptography route.  
Each cohort of students, in consultation with the Dean, Coordinator of ITCC and Head of
Mathematics, will decide (depending on numbers of students and available resources,
normally a minimum of three interested students will be required for a route to be
implemented) whether the whole class will take one of the two routes or whether the
class can be divided where some would take the Error Correcting Codes route while
others would take the Cryptography route.  The Error Correcting Codes route involves
modules MSC 6115 and MSC 6116 and will be taught during Semester 11 while the
Cryptography route involves MSC 6117 and MSC 6118 and will also be taught during
Semester 11.  The project work of Semester 12 will correspond with the route the
student has taken.

Assessment Criteria:
The MSc degree will be classified as follows:
•        Distinction
•        Credit
•        Pass
Details of the assessment process can be found at
MSc Assessment Criteria

Useful Books:

Coding and Information Theory, by
Steven Roman
Springer-Verlag 1992
ISBN 0-387-97812-7
ISBN 3-540-97812-7

Cryptography, Theory and Practice, by
Douglas R Stinson
CRC Press 1995
ISBN 0-8493-8521-0

Introduction to Information Theory and Data Compression, by
Darrel Hankerson, Greg A Harris and Peter D. Johnson
CRC Press 1998
ISBN 0-8493-3985-5

Introduction to Cryptography with Coding Theory, by
Wade Trappe and Lawrence C. Washington

The Theory of Error Correcting Codes, by
F J MacWilliams and N J A Sloane
Elsevier Science B.V. 1977
ISBN 0-444-85193-3

Introduction to Coding Theory, by
J H van Lint
Springer-Verlag 1992
ISBN 0-387-54894-7
ISBN 3-540-54894-7 (Berlin)

Convolutional Codes, An Algebraic Approach, by
Philippe Piret
The MIT Press 1988
ISBN 0-262-16110-9

Handbook of Coding Theory Volumes 1 and 2, by
V S Pless and W C Huffman, Editors
Elsevier 1998
ISBN 0-444-50088-X

A First Course in Coding Theory, by
Raymond Hill
Clarendon Press, Oxford, 1986
ISBN

Coding and Information Theory,
Richard W.Haming
Prentice-Hall Inc.,1986

Introduction to The Theory of Error-Correcting Codes, by
Vera Pless
John Wiley & Sons, Inc., 1982

Error-Correcting Codes and Finite Fields, by
Oliver Pretzel
Clarendon Press, 1992
ISBN 0-19-269067-1

Error Correcting Codes, a first course, by
Henk van Tilborg
Chartwell Brat, 1993
ISBN 0-86238-338-2

Elements of Algebraic Coding Theory
Lekh R. Vermani
Chapman and Hall, London, 1996
ISBN 0-412-57380-6

Coding Theory, A first Course
San Ling and Chaoping Xing
Cambridge University Press 2004
ISBN 0-521-52923-9

Algebraic Codes for Data Transmission
Richard E Blahut
Cambridge University Press 2003
ISBN 0-521-55374-1

Information Theory, Inference and Learning Algorithms
David J C MacKay
Cambridge University Press 2003
ISBN 0-521-64298-1

Acknowledgment:
  • In formulating this MSc course, useful discussions were held with Prof P.
    Fitzpatrick of University College Cork (UCC) of the National University of Ireland
    (NUI). The course outline follows closely a similar MSc course given at UCC,
    which was coordinated by Prof Fitzpatrick.  
  • We also wish to acknowledge the immense contribution which Prof E Schaefer of
    Santa Clara University, USA, has made and is continuing to make to this
    programme.
  • In 2009 Prof Michael Scott introduced the module Practical Cryptography which
    is helping us to make the practical application in banking institutions and
    industry.  We thank him for that important contribution.
Coding Theory
Mzuni
Maths
Coding
C
o
d
i
n
g

T
h
e
o
r
y
I
n
f
o
r
m
a
t
i
o
n

T
h
e
o
r
y