MATC16: Coding Theory and Cryptography (Spring 2011)

Instructor: Gábor Pete
Email: gpete at utsc dot utoronto dot the country we live in. I'm happy to answer questions in email.
Office: HW507A (take the stairs or elevator from the left side of the Market Place)
Phone (office): (416) 208 5110
Office hours: Thu 6-7 my office or BV 359, plus email.

Lectures: Tue 5-7 pm Thu 5-6 pm Room BV 260
Textbook: Introduction to CRYPTOGRAPHY with CODING THEORY (2nd edition) - by Trappe & Washington. Prentice Hall, 2006. For most of the course, the 1st edition is also fine, but expect some inconveniences, like missing exercises and sections. Several copies of the 2nd edition are available in the UTSC library.

Course plan:

Cryptography deals with communication over non-secure channels. Coding theory deals with communication over noisy channels. In real life they are often used together. The design of good crypto- and coding systems uses a lot of math, mainly number theory and algebra. Assessing the strength of these systems usually requires probability, information theory, complexity theory. We will discuss the most important topics of cryptography and coding theory, picking up the necessary math along the way. The topics will hopefully include:

I: Fundamental Principles of Cryptology; Classical Cryptosystems and Their Analysis
II: Modern Private Key Cryptosystems: Data Encryption Standard; Advanced Encryption Standard (Rijndael)
III: Public Key Encryption (e.g., RSA, discrete log based systems)
IV: Applications of Cryptography (e.g., digital signatures, security protocols, zero-knowledge identification, games)
V: Coding Theory (error correcting codes and cryptographic applications)
VI: Techniques from Number theory, Finite fields, Elliptic curves, Probability, Complexity Theory, Information Theory
VII: Quantum Computers

Evaluation:

Four HW assignments, one due every 3 weeks
Midterm Test
Final Exam

4 times 10%
25%
35%

The midterm test is on March 5, Saturday, 1-3 pm, in BV 516. Here is a summary of what the midterm might cover. And here are the solutions. The average score was 27.2/40.

The final exam is on April 12, Tuesday, 9-11 am, in MW 120. Here is a summary of what you should know for the exam. For practice, here is a previous final exam, and the solutions. And special office hour Monday 2:30-4:00 in my St George office, which is ES 4146, located in the Southwest corner of the 4th floor of the Earth Sciences building (corner of Russell and Huron).

The homework assignments will be posted here, about 10-14 days before their submission deadlines.

First assignment, due Feb 8, Tue. Here are the solutions. The average score was 15.7/20.
Second assignment, due March 3, Thu. It's a slightly longer assignment for a slightly longer time period, so it's worth 12%. Here are the solutions. The average score was 16.7/24.
Third assignment, due March 22, Tue. Worth 10.5%. Here are the solutions. The average score was 17.7/21.
Fourth assignment, due April 7, Thu. Worth 7.5%. Here are the solutions.

If you are lost with a homework problem, it is OK to ask for a bit of help from me, or discuss it with others and think together. However, you always should write up the solutions alone, with your own words.

Supplementary material:

Why the attack against Vigenere works.
Two proofs of the formula for Euler's phi function.

Here is the 2007 midterm test, from Prof Paul Selick.
Here is the 2009 midterm test and the solutions.

In 2009, the assignments included a project: an exposition exploring either a topic in Cryptology or Coding Theory which was not covered in lectures or going into more detail on a topic covered in lectures. Here are my project suggestions. These could be interesting to look at if you want to explore cryptography beyond the course material. Also, the extra topics for HW4 will be a subset of these.