Foundations of Cryptography

CS60088, Spring 2019, LTP: 3-1-0

Class Timings	WED: 10:00-10:55; THUR: 09:00--09:55; FRI: 11:00-12:55
Venue	CSE 108
Instructor	Somindu Chaya Ramanna
Teaching assistants	Titas Sarkar, Boyapally Harishma

Prerequisites

I assume basic familiarity with probability theory, algebraic structures (groups, rings, fields), linear algebra and algorithms. Some exposure to computational complexity is useful as well. These topics will not be covered in the course. No prior exposure to cryptography is necessary.

Syllabus (Tentative)

Introduction to Cryptography
Perfect secrecy -- definition, equivalent definitions, one-time pads, limitations of perfect secrecy, Shannon's theorem
Computational secrecy -- motivating the need for computational secrecy, formalising security under different threat models, reductionist arguments and hardness assumptions
Symmetric Encryption from psedorandom generators, pseudorandom functions and permutations
Introduction to one-way functions, constructing one-way functions from assumptions such as RSA, Discrete logarithm, hard-core predicates, construction of pseudorandom objects from one-way functions
Message authentication codes (MACs), hash functions and their security definitions, provably secure constructions
Practical Constructions of symmetric encryption, MACs and hash functions
Public key encryption

References

Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, Chapman and Hall/CRC Press, 2007.
Shafi Goldwasser and Mihir Bellare, Lecture Notes on Cryptography, 2008 (available here).
Oded Goldreich, The Foundations of Cryptography, Volume 1 and Volume 2, Cambridge University Press, 2001 and 2004.
Wenbo Mao, Modern Cryptography: Theory and Practice, first edition, Pearson Education, 2004.

Evaluation

The evaluation for this course will be based on the mid-sem, end-sem examinations and a term paper. Details are below.
350%: end-sem exam
25%: mid-sem exam
40%: term paper

Tests/Exams

[Test questions and solutions will be uploaded here.]

Term paper + Presentation

Below is a list of topics for the term paper. You are free to choose any topic outside of this list. Evaluation will be done based on a report and a 30-minute presentation. The report (prepared in Latex) should discuss in detail atleast one non-trivial result with a complete analysis. It should be self-contained with an introduction explaining the importance of the topic. Pay attention to language aspects such as grammar and spelling. You are allowed to use material from other sources. But, you must understand and express in your own language and provide proper references. Directly copying from other sources is forbidden and will be heavily penalised.

Evaluation criteria are as follows.

Report:

relevance of the topic chosen to the course,
introduction,
clarity of exposition,
content covered,
insights/criticisms/comments of your own, if any.

Presentation:

level of understanding,
clarity of presentation,

Deadline for choosing a topic: ~~1st March, 2019~~ 3rd March 2019, 23:59 IST
(Strict) Deadline for submission of report: 4th April 2019 06:00 IST (Anything received after the deadline will not get any credit.)

Presentations will be scheduled in the 1st and 2nd weeks of April (possibly during the weekends).

Once you choose a topic, send me an email with the subject line FoCry Term Paper - Choice of Topic clearly stating the following in the main text: your choice of topic, roll number and full name.

List of Topics:

Key Management for Symmetric Key Encryption Systems
~~Public Key Infrastructre and Certificate Management~~
Number Theoretic Construction of Pseudorandom Generators
~~Number Theoretic Construction of Pseudorandom Functions~~
~~Zero Knowledge Proofs~~
Lossy Trapdoor Functions
Hash Proof Systems
Constrained Pseudorandom Functions
Commitment Schemes
Identification Schemes
~~Multi-party computation~~
~~Authenticated Encryption~~
~~Homomorphic Encryption~~

Tutorials

Tutorial 1 Questions Solutions

Tutorial 2 Questions Solutions

Tutorial 3 Questions Solutions

Tutorial 4 Questions Solutions

Tutorial 5 Questions Solutions

Tutorial 6 Questions Solutions

Note: There will be no evaluation for the tutorials. The purpose is for you to get more exposure and be able to solve problems independently. DO NOT search for solutions online during these sessions. Instead try to come up with the solution independently or via discussions with the TA's/classmates.