Breaking News:
Dr Khumbo Kumwenda is now the Coordinator of the
ITCC Programmes .
Email: <Dr Khumbo Kumwenda <khumbo@aims.ac.za>;>
See below for details of ITCC Programmes.
A PhD in Coding Theory is being introduced at
Mzuni. Check it out at: PhD in ITCC Programme
The MSc in Information Theory,
Coding and Cryptography (ITCC)
From 2004 to 2009 twenty nine students have graduated from the
programme. Of these twelve 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. Three joined the programme in 2010.
Graduates who have progressed
to PhD Studies in Coding Theory:
All of the above four have got full funding for their PhD studies.
International Input:
1) Prof Michael Scott, Dublin City University College, is supervising three
students. He is also supervising one graduate of the programme who is doing
his PhD in Coding Theory.
2) Prof Ed Schaefer, Santa Clara University, is supervising three students.
He is due to come to Mzuzu again during July and August of 2010. This will be
his fourth visit to Mzuzu.
3) Since the programme began in 2004 no less than six international
experts have come to Mzuzu and given courses in Coding Theory. Their stay
at Mzuzu varied from three months to thirteen months.
4) Prof Eric Mwambene, University of the Western Cape, is acting as an
advisor to the programme. He is also supervising one graduate of the
programme who is doing a PhD in Coding Theory.
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. At any of the WCCs
(Workshops on Coding and Cryptography --- which are international workshops held in
France and funded by INRIA, a French research institute) since their inception in 1999 it is
only Mzuzu University which has represented Africa. Mzuzu University was also the sole
African participant at the International Symposium in Information Theory 2004 (ISIT 2004)
which was held in Chicago 29 June to 3 July 2004 and funded mainly by the renowned
International Association of Electrical and Electronic Engineers (IEEE). Yet again Mzuzu
University represented Africa at the Western European Workshop on Research in
Cryptology (WEWORC) in 2007. Furthermore in the 2,169 pages of the Two Volume 1998
Handbook of Coding Theory there is no contribution from Africa. Within Southern Africa it is
Mzuzu University together with the University of ZwaZulu Nathal who feature prominently in
presenting papers in Coding Theory at International Conferences like ICT 2005 which was
held in Capetown and AFRICON 2007 which was held in Namibia. Mzuzu University sent 7
students to the Southern Africa Mathematics and Science Association (SAMSA) 2005 which
was held in Blantyre, each student presenting his/her paper. Two from Mzuzu University
presented papers at SAMSA 2006. Mzuzu University again sent 8 students, each student
presenting his/her own paper, to the SAMSA 2008 Conference which was held in Maputo
and again sent 6 students to SAMSA 2009 which was held in Dar es Salaam, again each
student presenting his/her own paper. In 2008 at SAMSA in Maputo Nephtale Mumba
scooped one of the two awards for the best student presentation. See Report on
SAMSA 2008.
Coding Theory:
Coding Theory is essentially about putting information in codes. There might be several
reasons why information would need to be coded.
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 Degree:
MSc in Information Theory, Coding and Cryptography (ITCC).
Course Coordinator:
Prof J.A. Ryan, PhD assisted by Prof E. Schaefer PhD.
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.
Outside Input:
The following have been in residence at Mzuzu University and given input to the program
1. Prof Patrick Fitzpatrick (University College Cork of the National University of Ireland)
2. Prof Edward Schaefer (Santa Clara University, USA)
3. Dr Katie O'Brien (Bristol University, UK)
4. Dr Eimear Byrne (University College Dublin of the National University of Ireland)
5. Dr Carl Bracken (Third Level Institute for Technology, Kevin Street, Dublin, Ireland)
6. Prof Michael Scott (Dublin City University)
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:
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 and weighting:
Each of the six modules will be assessed by 1) two Continuous Tests each lasting one
hour and a half and 2) a 3-hour Final Examination, each module being examined on its
completion. The Continuous Testing will contribute 40% and the Final Examination will
contribute 60% of the module marks.
A student who is not exempted from the Bridging Course will have to pass the two modules
of the Bridging Course before proceeding to Semester 10. The following is the grading
system which will be applied to the Bridging Course:
45 – 100 Pass
0 – 44 Fail
The MSc Degree will be assessed on the work of Semesters 10, 11 and 12. Each of the
four modules of Semesters 10 and 11 will contribute 15% of the overall marks. The
project/thesis will contribute 40% of the overall marks.
The following is the grading system which will be used.
Fail Pass Credit Dist
0% - 45% 45% - 54% 55% - 69% 70% and over
The MSc degree will be classified as follows:
• Distinction
• Credit
• Pass
A Distinction is awarded to a student with a minimum mean overall mark of 70% or over.
A Credit is awarded to a student with a mean overall mark in the range of 55% to 69%.
A Pass is awarded to a student with a mean overall mark in the range of 45% to 54%
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:
Dr Khumbo Kumwenda is now the Coordinator of the
ITCC Programmes .
Email: <Dr Khumbo Kumwenda <khumbo@aims.ac.za>;>
See below for details of ITCC Programmes.
A PhD in Coding Theory is being introduced at
Mzuni. Check it out at: PhD in ITCC Programme
The MSc in Information Theory,
Coding and Cryptography (ITCC)
From 2004 to 2009 twenty nine students have graduated from the
programme. Of these twelve 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. Three joined the programme in 2010.
Graduates who have progressed
to PhD Studies in Coding Theory:
- Dr Khumbo Kumwenda graduated in 2011 with a PhD in Coding Theory
from the University of the Western Cape in South Africa - Dr Ezekiel Kachisa graduated with a PhD from Dublin City University in
Ireland in 2011 - Michael Zimba is doing his PhD at the College of Computer and
Communication, Hunan University, China. - Mrs Mwai Nyirenda-Kayuni is pursuing PhD studies in Cryptography in
Korea
All of the above four have got full funding for their PhD studies.
International Input:
1) Prof Michael Scott, Dublin City University College, is supervising three
students. He is also supervising one graduate of the programme who is doing
his PhD in Coding Theory.
2) Prof Ed Schaefer, Santa Clara University, is supervising three students.
He is due to come to Mzuzu again during July and August of 2010. This will be
his fourth visit to Mzuzu.
3) Since the programme began in 2004 no less than six international
experts have come to Mzuzu and given courses in Coding Theory. Their stay
at Mzuzu varied from three months to thirteen months.
4) Prof Eric Mwambene, University of the Western Cape, is acting as an
advisor to the programme. He is also supervising one graduate of the
programme who is doing a PhD in Coding Theory.
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. At any of the WCCs
(Workshops on Coding and Cryptography --- which are international workshops held in
France and funded by INRIA, a French research institute) since their inception in 1999 it is
only Mzuzu University which has represented Africa. Mzuzu University was also the sole
African participant at the International Symposium in Information Theory 2004 (ISIT 2004)
which was held in Chicago 29 June to 3 July 2004 and funded mainly by the renowned
International Association of Electrical and Electronic Engineers (IEEE). Yet again Mzuzu
University represented Africa at the Western European Workshop on Research in
Cryptology (WEWORC) in 2007. Furthermore in the 2,169 pages of the Two Volume 1998
Handbook of Coding Theory there is no contribution from Africa. Within Southern Africa it is
Mzuzu University together with the University of ZwaZulu Nathal who feature prominently in
presenting papers in Coding Theory at International Conferences like ICT 2005 which was
held in Capetown and AFRICON 2007 which was held in Namibia. Mzuzu University sent 7
students to the Southern Africa Mathematics and Science Association (SAMSA) 2005 which
was held in Blantyre, each student presenting his/her paper. Two from Mzuzu University
presented papers at SAMSA 2006. Mzuzu University again sent 8 students, each student
presenting his/her own paper, to the SAMSA 2008 Conference which was held in Maputo
and again sent 6 students to SAMSA 2009 which was held in Dar es Salaam, again each
student presenting his/her own paper. In 2008 at SAMSA in Maputo Nephtale Mumba
scooped one of the two awards for the best student presentation. See Report on
SAMSA 2008.
Coding Theory:
Coding Theory is essentially about putting information in codes. There might be several
reasons why information would need to be coded.
- 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. - 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. - 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 Degree:
MSc in Information Theory, Coding and Cryptography (ITCC).
Course Coordinator:
Prof J.A. Ryan, PhD assisted by Prof E. Schaefer PhD.
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.
Outside Input:
The following have been in residence at Mzuzu University and given input to the program
1. Prof Patrick Fitzpatrick (University College Cork of the National University of Ireland)
2. Prof Edward Schaefer (Santa Clara University, USA)
3. Dr Katie O'Brien (Bristol University, UK)
4. Dr Eimear Byrne (University College Dublin of the National University of Ireland)
5. Dr Carl Bracken (Third Level Institute for Technology, Kevin Street, Dublin, Ireland)
6. Prof Michael Scott (Dublin City University)
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’
- MSC5104 follow closely written notes by Prof E. Schaefer
- MSC5115 follows the last five chapters of ‘Coding Theory, A first Course’
- MSC6116 follows closely Thesis on Goppa codes by Prof J.A. Ryan.
- 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 and weighting:
Each of the six modules will be assessed by 1) two Continuous Tests each lasting one
hour and a half and 2) a 3-hour Final Examination, each module being examined on its
completion. The Continuous Testing will contribute 40% and the Final Examination will
contribute 60% of the module marks.
A student who is not exempted from the Bridging Course will have to pass the two modules
of the Bridging Course before proceeding to Semester 10. The following is the grading
system which will be applied to the Bridging Course:
45 – 100 Pass
0 – 44 Fail
The MSc Degree will be assessed on the work of Semesters 10, 11 and 12. Each of the
four modules of Semesters 10 and 11 will contribute 15% of the overall marks. The
project/thesis will contribute 40% of the overall marks.
The following is the grading system which will be used.
Fail Pass Credit Dist
0% - 45% 45% - 54% 55% - 69% 70% and over
The MSc degree will be classified as follows:
• Distinction
• Credit
• Pass
A Distinction is awarded to a student with a minimum mean overall mark of 70% or over.
A Credit is awarded to a student with a mean overall mark in the range of 55% to 69%.
A Pass is awarded to a student with a mean overall mark in the range of 45% to 54%
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
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
n
f
o
r
m
a
t
i
o
n
T
h
e
o
r
y
 |  |  |  |  |  |  |