## CS 290G: Introduction to Cryptography (Fall 2014)

**Instructor:** Huijia
(Rachel) Lin,
rachel.lin(at)cs(dot)ucsb(dot)edu

**Class time and location:** TR 3-4:45pm, Phelp 2510

**Office hours:** Thursday 1:30-2:30pm or by appointment, HFH 1153

**Class
webpage:** http://www.cs.ucsb.edu/~rachel.lin/courses/14f290G/

## Announcement

Dec. 11th: **The final is here [pdf] [tex].**

Dec. 4th: Final will be out on **Thursday Dec. 11th** at
midnight and will be due on Thursday Dec. 18th at midnight.

Dec. 4th: The las class on Dec. 11th is cancelled. Instead, I will hold longer office hour from 1:30pm to 3:30pm at 1153 HFH. You can also pick up your last homework at that time.

Dec. 4th: ** There has been an error in the third
homework: In part 2, task a), the hash function should be
length-halving, instead of compressing by only one bit. The
new versions are here. [pdf] [tex].**

Dec. 2nd: **The third homework
is here [pdf] [tex].**

Nov. 13th: **The second homework
is here [pdf] [tex].**

Nov. 4th: Class on Nov. 6th (Thursday) is cancelled. Next class is on Nov. 13th (Thursday)

Nov. 4th: **Schedule of homeworks and final:** Homework 2 will be
posted on Nov. 13th (Thursday). Homework 3 will be posted on
Dec. 2nd (Tuesday). Final will be posted on Dec. 12th
(Friday). All homeworks and final will be posted at
mid-night, and due on mid-night one week after.

Oct. 25th: In the first homework, Task 3 (b), x1 and x2 are of the same length.

Oct. 23rd: The first homework is here [pdf] [tex].

The first homework will be available for downloading at midnight 11:59pm Thursday Oct. 23rd. The homework will be due in 7 days, 11:59pm Sunday Oct. 30th.

### Course Description

Cryptography provides important tools for ensuring the security of modern digital systems and the privacy of the sensitive information involved in them. Nowadays, core cryptographic tools, such as, encryption, digital signature, key agreement protocols, are used behind millions of daily online transactions. This course will give an introduction to the development and application of cryptographic tools.

We will focus on the foundation of cryptography. The first and foremost questions to ask are philosophical: "What does it mean that a cryptographic tool, say encryption, is secure?", "Is security possible?", "What makes cryptographic tools trustworthy?". Since the 70's, Modern cryptography developed the mathematical language to articulate these questions, as well as the formal method to answer them. Various cryptographic tools and systems are then developed using the mathematical language and their security guarantees are rigorously reasoned about using the formal method. In this class, we study the mathematical underpinning of cryptography and core cryptographic tools developed upon it.

**Course Objectives:** The main objective is to introduce
core cryptographic tools, and cryptographic reasoning. Through the lens of cryptography, students
will also develop, in general, the capability of critical thinking
and reasoning of complex systems.

**Required background:** This class will take a rigorous approach:
Exposure to basic probability, algebra / elementary number theory and complexity theory
is expected. The class also requires a certain level
of mathematical maturity (students should be ready to understand
mathematical proofs, and to write simple ones). __If in doubt,
contact the instructor!__

**Course Set-ups and Textbook** The course consists of two
lectures each week. There is no textbook required, but the following resources are
instrumental

- O. Goldreich. The Foundations of Cryptography
- J. Katz and Y. Lindell. Introduction to Modern Cryptography
- R. Pass and a. shelat. A Course in Cryptography (Lecture Notes)
- M. Bellare and P. Rogaway. Introduction to Modern Cryptography (Lecture Notes)

**Grading:**

Final grade will depend on three components: (1) Class
scribe notes and class paticipation (2) 3-4 homeworks and (3) one take
home final. The
class scribe notes and class participation account for 1/6 of the
grade, homeworks account for 1/2 of the grade, and the take home
final accounts for 1/3 of the grade. **Quality of exposition will impact score.**

**Class Policy:**

__ Homework Policy:__ For each homework, you are free to collaborate with one
other student in class. But you are required to write down solutions
individually and acknowledge your collaborator. You may reference
published material, but again you must acknowledge all sources you
use. While collaboration and referencing is allowed, it is a violation of
this policy if you are unable to explain your solution orally to
me.

__ Scribe Policy:__ Each class will be scribed by one student, and it is due
one week after the class.

__ Final Policy:__ You must complete the final on your own without
collaboration or refrencing public material.

Typed solutions and scribe notes are required.

__ Late-days Policy:__ Each student has a total of 7 "late-days", you are free to use them
throughout the quartor to legitimately hand in homework solutions and
scribe notes after their due days. To use late-days, you need to
send me an email before the deadline to notify me how many late-days
you intend to apply. Being late without notification or after 7
late-days are used up will lead to halfing the grade for that
solution or scribe note.

### Topics

The following is a rough list of topics to be covered in the class. There will be changes depending on the pace of the class.

- Overview of modern cryptography
- Information Theoretic Security
- Computational Hardness and one-way functions (OWF)
- Pseudo-random generation (PRG) and Pseudo-random functions (PRF)
- Private key encryption and public key encryption schemes

- Authentication: Digital Signature, Message Authentication Codes. Hash Functions
- Zero-Knowledge
- Secure Multi-party Computation

### Scribe Notes

The scribe notes are rough notes of the lectures. It is intended to help students to recall the content of the lecture. (Think of notes you keep for yourself). To maintain consistency in styles, please use this LaTeX template.

- Lecture 0: Introduction
- Lecture 1: Perfect Security and One-time Pad. Scribe for Lecture 1 by John Retterer-Moore
- Lecture 2: Models of Computation and One-way Functions. Scribe for Lecture 2 by Binyi Chen
- Lecture 3: Hardness of Factoring implies Weak OWF. Scribe for Lecture 3 by Asad Khalid
- Lecture 4: Hardness Amplification: Weak OWF implies Strong OWF. Scribe for Lecture 4 by Nilo Redini
- Lecture 5: RSA OWFs. Scribe for Lecture 5 by Harichandan Pulagam
- Lecture 6: Computational Indistinguishability. Scribe for Lecture 6 by Tiawna Cayton
- Lecture 7: Hard-core Predicate and Construction of PRG with 1-bit Expansion. Scribe for Lecture 7 by Leonardo Bohac
- Lecture 8: Construction of PRG with poly-bit Expansion. Scribe for Lecture 8 by Markus Karl Torfason
- Lecture 9: Multi-message security and PRF.Scribe for Lecture 9 by Jason Berry
- Lecture 10: PRF revisited, multi-message secure secret-key encryption from PRF, and Block-ciphers.Scribe for Lecture 10 by John Retterer-Moore
- Lecture 11: Construction of PRF from PRG. Definition of Public Key Encryption.Scribe for Lecture 11 by Binyi Chen
- Lecture 12: Trapdoor Permutations (TDPs) and Construction of PKE from TDPs.Scribe for Lecture 12 by Markus Karl Torfason
- Lecture 13: Message Authentication. MAC and Digital signatures. Construction MAC and one-time signaturesScribe for Lecture 13 by Harichandan Pulagam
- Lecture 14: Domain Extension, and many-time secure signaturesScribe for Lecture 14 by Nilo Redini
- Lecture 15: Knowledge. Definition and examples of ZK proof system.Scribe for Lecture 15 by Tiawna Cayton
- Lecture 16: GMW Construction of ZK proof system.Scribe for Lecture 16 by Asad Khalid