EE 720 - Introduction to Number Theory and Cryptography

EE 720 - Introduction to Number Theory and Cryptography

Instructor:

Prof Saravanan Vijaykumaran

Motivation to take this course:

This course focuses more on the theoretical aspects of cryptography, while spending a considerable time on the math behind different cryptographic protocols & algorithms. So, if one is interested in maths, likes to prove theorems & lemmas and wishes to explore cryptography, this is the course to start with. For me, after developing on different blockchains, I wished to understand the core principles & theoretical aspects related to cryptography that forms the basis of a blockchain network.

Sections:

Just a single section. Although it is a 7xx course, it was taken up by a large number of UGs.

Semester:

Spring ‘19

Course Difficulty:

The course is full of proving theorems & justifying arguments as to why any given cryptographic scheme is secure or not. So once the student gets hold of the fundamental concepts, higher level proofs automatically start falling in place. But the course is definitely math heavy, with introduction to modular arithmetic & group theory. So, for those who enjoy maths, this course may turn out to be a breeze, while for others, a decent amount of effort needs to be put in to secure a decent grade. I would rate the course difficulty as 7/10.

Time commitment required:

Lectures account for 3 hours per week for this course. If one pays careful attention & grasps enough content in class, around 2-3 hours per week on self study should be sufficient. This could be in the form of going through the prescribed textbook & solving some questions. The 5 assignments in the course had a deadline of about a week and could be completed in 1-2 hours.

Attendance Policy:

Attendance was taken on 14 occasions randomly during the semester wherein TAs would come & scan the students’ ID cards during the lecture. Students with 10+ occurrences during the attendance were awarded 5 marks, and then on for “n” occurrences (n < 10), “n/2” marks were awarded.

Grading Policy and Statistics:

The grading was pretty healthy in 2019, with 13 AA’s (cutoff ~90), 26 AB’s (cutoff ~80) and the remaining to also follow similarly. There were no FR’s awarded.

Prerequisites:

No hard prerequisites as such for this course. However, any prior knowledge of number theory, modular arithmetic or group theory could be a huge bonus.

Evaluation Scheme:

5% Attendance, 10% Assignments, 20% Quizzes, 25% Midsem, 40% Endsem For AU, final score should be at CC level or above.

Course Contents (in brief):

The course kicks off with fundamental definitions of secrecy, threat models & touches upon some historical ciphers. This builds a base to introduce the concepts of “Perfect Secrecy”, “Computational Security” & “Private Key Encryption” schemes. It includes proving how different encryption schemes could be secure against some forms of attack, but not against others. The course progresses to talk about “Message Authentication Codes”, “ Authenticated Encryption” & practical realizations of these schemes using “Stream & Block Ciphers”. Post midsem, we switched gears to talk in detail about Number Theory, Modular Arithmetic & basics of Group Theory, which laid the foundations for understanding “Public Key Encryption” schemes, which was the immediate next topic. Towards the last leg of the course, we discussed “Hash Functions”, their implementation & briefly touched upon “Digital Signatures”.

Mechanism of Instruction and Teaching Style

Throughout most of the course, the professor explained & proved stuff in detail on the blackboard, with students following along & making notes. He used to upload brief class notes after the lectures on the course homepage, with clear references to the sections of the Reference Book that students were supposed to look up for details about each topic. Slides were used occasionally (maybe just 1-2 lectures in the semester) to explain some practical concepts.

Feedback on Tutorials/Assignments/Projects etc

There were no tutorials or projects for this course. However, a set of 5 assignments (4-5 questions each) were spread across the semester & accounted for 10% of the grade. If basic concepts & mathematical formulation was clear, these assignments were pretty doable.

How strongly would you recommend someone for taking this course?

For a student who wants to explore the space of cryptography, this course would definitely be recommended. However, one thing to note is that this course can be typically considered as “theoretical” cryptography, with a lot of maths involved. So if one is looking for a course to dive into more practical aspects which involve more exposure on “doing” things to see how security works, this may not be the best course (in that case, feel free to check out CS406: Cryptography and Network Security).

When did you take this course? What will be the ideal semester to take this course? Any other course which can be done before this?

I took it up in my 4th semester (Spring ‘19). There is no such restriction on which semester to take this up because the class had a good mix from all years (2-4 year B.Tech & M.Techs). It would completely be based on one’s course load in the semester & enthusiasm to delve into Cryptography.

Feedback on Exams:

All the exams (Quizzes, Midsem & Endsem) were of a “Moderate” level, & were intended to completely test the problem solving skills of students. Most questions involved proving if a scheme is secure to a particular form of attack or not, proving some theorems/lemmas that were left unproved during the lectures & later, some problems on modular arithmetic & group theory (including the proofs & direct applications of important theorems like Lagrange’s theorem, Chinese Remainder Theorem, etc.)

References used:

Primary Reference: Introduction to Modern Cryptography, Jonathan Katz and Yehuda Lindell, CRC Press, 2015 (2nd Edition) Secondary Reference: A Computational Introduction to Number Theory and Algebra, Victor Shoup, 2008 (2nd edition) The solutions to the problems in the Primary Reference are not available directly, but can be hunted for in the solutions to exams/assignments of previous offerings of this course at IIT Bombay, as well as the corresponding course at UC Berkeley.

Review by: Tezan Sahu