ICS 201: Introduction to Cryptography

CS 201: Introduction to Cryptography

Fall Quarter, 2007

· Class time: M-W, 3:30-5

· Room: ICS 243

· Prerequisites: ICS 6A and ICS 161/261, also see below

· Textbook: Jonathan Katz, Yehuda Lindell,"Introduction to Modern Cryptography".

· Office hours: Tuesday and Thursday 10:30-12. I'm also usually around most of the time, except lunch hour and 2-3 MWF when I teach ICS.6D, and you are welcome to stop by anytime. I always keep an open door and if I'm talking to someone I can interrupt and answer a quick question or at least arrange some other time you can stop by. You can also email me first at stasio@ics.uci.edu, or check if I'm in my office before you come, at extension x4-8878. I very much encourage you to use the office hours and ask me to explain things you don't understand.

Course Schedule:

Week	Dates	Homework	Subjects	Reading
Week 1	Oct 1		· Intro to Modern Cryptography · Classical Cryptosystems	Chapter 1 (except section 1.3, which is optional) Chapter 2 (except section 2.4, which is optional)
Week 2	Oct 8	Hmw1 / Solutions1	· Private-Key Encryption: Definition and its Implications	Chapter 3, Sections 3.1 and 3.2. In Wednesday lecture we gave as one implication the hardness of predicting any particular bit of a random plaintext. This proof is in the textbook as a proof of Claim 3.10.
Week 3	Oct 15		· Pseudorandom Number Generator · Encryption of Fixed-Length Messages · Stream Cipher	Sections 3.3 and 3.4
Week 4	Oct 22	Hmw2 / Solutions2	· Chosen Plaintext / Ciphertext Security · Pseudorandom Functions · (Strong) Pseudorandom Permutations · Modes of Operation of a Block Cipher	Sections 3.5 - 3.7, example of hybrid argument in the proof of proposition 3.22
Week 5,6	Oct 29 – Nov 5	Hmw3	· Message Authentication Codes [MACs] · Collision Resistant Hash functions · Correct order of MAC and Encryption, MAC + CPA encryption => CCA encryption	Chapter 4
Week 7	Nov 11		· One-Way Functions · Hard-Core Bit of OWFs, OWF => PRG	Sections 6.1, 6.2, 6.4. Optionally Section 6.3.
Week 8	Nov 19
Week 9	Nov 26
Week 10	Dec 3

Additional reading material:

Reading link

Course Description:

This course is an introduction to modern cryptography and security for graduates and advanced undergraduates. The class will try to balance between the breadth of the coverage and an attempt to develop a general approach to the study of security issues. The first aim of the class is to introduce students to various cryptographic tools like symmetric and public-key encryption schemes, signature schemes, message authentication schemes, identification protocols, and others. The second and equally important aim of this class is to develop a "provable-security" paradigm of approaching any communication security problem. This paradigm consists of (1) understanding the security *goal* of any protocol, i.e. understanding what properties a protocol needs to achieve to be considered secure, and (2) designing a protocol together with a *proof* that the protocol achieves these properties under some well-understood computational hardness assumptions, for example under the assumption that it is computationally hard to factor large composite numbers.

The aim of the course is to introduce some fundamental cryptographic tools in such a way so that (1) you will be able to specify the security needs of the system you are designing and use existing cryptographic mechanisms in such a way so that your security needs are met, and (2) you will be able to develop new cryptographic mechanisms and protocols yourself.

To help further these goals, we'll end the class with conference-style presentations by the *graduate* students on some security/cryptography topic chosen by the student.

What this class is not about:

This class will not teach you all there is to know to make computers and networks secure. Cryptography is only one layer in the stack of engineering issues that need to be solved to make computers and networks secure. Computer security deals with lots of issues we will not touch on in the class, like buggy code, viruses, denial of service attacks, network monitoring techniques, preventing bad passwords, integrating various network services securely, and many more. This class will stay firmly on the layer of algorithms for the so-called "cryptographic primitives", i.e. the design of cryptographic tools like encryption, signatures, authentication. While some of these tools will be probably very useful in solving any of the real-world security issues above, we will not be analyzing any such systems in this class. On the other hand, we will often mention the real-world security issues like those listed above in motivating the security properties required of the cryptographic tools we will be designing.

Another note of warning is that in this class we will not concentrate on techniques used to design and analyze block ciphers (like DES or AES) and hash functions (like MD5 and SHA), although the class will offer you some insight into security of such constructions. We will focus instead on public key crypto, but we will spend a few lectures on private key algorithms too.

Grading policy:

70% problem sets
30% take-home final

Problem sets are due at the beginning of the class. You are allowed to work on the homework problems together with other students, but you have to write down all solutions independently and acknowledge whom you worked with. You are allowed to consult other sources, such as textbooks, lecture notes for this or similar classes, research papers, etc, but you must clearly acknowledge any material you reference.

Prerequisites:

The formal prerequisites are ICS 6.A and ICS.161. However, what you really need in general is this:

You cannot be “math-phobic” or “theory-phobic”. The major focus of this class is on definitions and proofs, and we’ll use probability and number theory in the running time analysis and the security analysis of the algorithms we will study.

More specifically, you need the following:

You should be comfortable with proofs, with elementary probability, and have the basic knowledge of discrete math used in computer science (e.g. ICS.6A).
It's highly recommended that you have some algorithms class (like ICS.161), and that you are familiar with asymptotic analysis of algorithm running time.
It'd be also easier for you if you took a computability/complexity class like ICS.162, so you are familiar with the notion of polynomial-time algorithms, and the notion of a reduction between computational problems. However, this is material which we'll go over in this class to the extend that we'll use it, and I believe that you can pick it up easily.
You do not have to know modular arithmetic, because we will review everything we will need. However, familiarity with it will be helpful. If you want to learn modular arithmetic on a deeper level, consider the MATH.173A class taught every fall quarter by prof. Caryl Margulies in the math department (see also below).