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/


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

Additional reading material will be communicated during class.


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.


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.

Basic primitives:
  • 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
Advanced primitives
  • 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