CS 178: Introduction to Cryptography (Winter 2015)

General Information

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


  • Asad Ismail, asad(at)cs(dot)ucsb(dot)edu
  • John Retterer-Moore, retterermoore(at)cs(dot)ucsb(dot)edu

Time and location:

  • Class: Tuesday/Thursday 5-6:15pm, GIRV 2128
  • Session 1: Friday 11:00-11;50am, PHELP 1444
  • Session 2: Friday 12:00-12:50pm, GIRV 1116

Office hours:

  • Asad Ismail: Monday 2:00-4:00pm, Graduate Student Lounge (GSL) in front of HFH
  • John Retterer-Moore: Wednesday 5:00-7:00pm, Trailer 136 Room 104
  • Rachel Lin: Friday 3:30pm-4:30pm, HFH 1153

Piazza: We will be using Piazza for class-related discussions. The Piazza page for this class is available at https://piazza.com/ucsb/winter2015/cs178/home.


  • Mar 3rd : The last class on Mar 12th will give review for the final. The sections on Mar 13th are canceled.
  • Mar 3rd : Homework 5 is out and is due on March 10th.
  • Feb 24th : Homework 5 is delayed to be out on March 10th.
  • Feb 17th : The office hour on Friday, Feb 20th, from 3:30 to 4:30pm is cancelled.
  • Feb 17th : Homework 4 is out (see syllabus below). It is due at 5:00pm on Feb 24th.
  • Feb 8th : Solution of Homework 2 is out (see below and Piazza).
  • Feb 6rd : Homework 3 question 1 has a typo inside. The ciphertext should have m+1 blocks instead of m blocks, thus from C[0] C[1] to C[m].
  • Feb 3rd : Homework 3 is out (see syllabus below). It is due at 5:00pm on Feb 12th.
  • Jan 29th : Solution of Homework 1 is out (see syllabus below and Piazza).
  • Jan 22th : Homework 2 is out (see syllabus below). It is due at 5:00pm on Jan 29th.
  • Jan 21th: Change of Office Hour time! Rachel's office hour has been changed to Friday 3:30pm to 4:30pm to avoid conflicting with the discussion sessions.
  • Jan 15th: Correction to the homework! Exercise 5 in the homework is the exercise 1.21(a) in the textbook. Some text that provides clues for decrypting the ciphertext was missing in the homework. The corrected version is here! (You can also download the correct version from the syllabus below.)
  • Jan 13th : Homework 1 is out (see syllabus below). It is due at 5:00pm on Jan 20th.
  • Jan 8th : We are going to start enrolling more students as soon as rooms become available. Students who are currently not enrolled but interested in attending the class please send an email to Asad at asad(at)cs(dot)ucsb(dot)edu. In your email, please include evidence (e.g., transcript and explanation) that you fulfill the pre-requisite.
  • Jan 8th : We have sent out invitation for Piazza to registered students. If you have not received an invitation, or are currently not enrolled but still in class, please send an email to John retterermoore(at)cs(dot)ucsb(dot)edu.

Course Description

Cryptography provides important tools for ensuring the privacy, authenticity, and integrity of the increasingly sensitive information involved in modern digital systems. Nowadays, core cryptographic tools, including encryption, message authentication codes, digital signature, key agreement protocols, etc., are used behind millions of daily on-line transactions. In this course, we will unveil some of the "magic" of cryptography.

Modern Cryptography uses mathematical language to precisely pin down elusive security goals, design primitives and protocols to achieve these goals, and validate the security of designed primitives and protocols using mathematical proofs based on clearly stated hardness assumptions. Therefore, to learn cryptography, it is essential to understand its mathematical underpinning. In this class, we will see the inner-working of cryptography for several core cryptographic tools, from encryption, to message authentication codes, to hash functions, to digital signatures, etc.

Clarification: This class focuses on the foundation of cryptography. This class is not about learning all cryptographic acronyms or all cryptographic protocols in use today, nor about familiarizing with current implementations of cryptographic tools, and issues that arise when implementing cryptographic tools. Furthermore, this class is certainly not going to cover the more extensive topic of computer security. In particular, this class will not teach you about firewalls, malware detection, nor how to secure or hack a system. Rather, the class will strive to convey the ideas and principles behind cryptographic design, and cryptographic applications.

Required background: Though the presentation in this class will largely remain at an intuitive level, the class still requires a certain level of mathematical maturity (students should be ready to understand mathematical definition and proofs, and to write simple ones). Exposure to basic probability, algebra / elementary number theory and theory of computing is also expected. If in doubt, contact the instructor!

Textbook and Resources

The class will combine the following textbook by D. Stinson, and the lecture slides by Mihir Bellare. Additional great resources that will help you to learn are:


There will be five homework, one midterm exam, and one final exam. Each homework accounts for 20 points, midterm 30 points, and final 40 points. In total, there are 170 points. Your final grade will depend on the weighted total points.

Class Policy:

  • Every homework will be posted on-line on days indicated below in the syllabus at 11:59pm PST, and are due on days indicated below at 5:00pm PST. The homework can be submitted at the beginning of the class or to the homework box in the CS mail room.
  • No late homework are accepted, unless with the consent of the intrusctor before the due time. You might be asked for documents as evidence to justify the need of late days.
  • You may discuss about homework with your classmates, but you must write down your own solution and acknowledge your collaborators.
  • The midterm and final exams must be completed independently. The only material allowed during the exam are 2 pages of hand-written notes. If additional material is allowed, the instructor will communicate before the exams.


The following is a rough list of topics to be covered in the class. This list will be changed and refined during the course depending on the pace of the class. I will also post more detailed bullets of content covered after every class, as well as material to be read.

1 2015-01-06
  • Welcome to class
  • Introduction to Cryptography
  • Secure communication
  • privacy, authenticity, integrity
  • Why is cryptography hard?
  • Classical Ciphers
2 2015-01-13
  • One-time pad
  • Shannon's perfect security
  • Lecture 3 slides
  • Stinson Textbook 2.2-2.3
  • Note: The definition of perfect security in the book is different
    from that in Lecture slides. But they are mathematically equivalent.
  • Note: Book shows that shift-cipher has perfect security when a new random key is used for every letter encrypted. In this case,
    shift-cipher is similar to one-time-pad, just over a larger alphabet
  • Limitation of perfect security
  • Block cipher and their cryptanalysis
3 2015-01-20
  • AES
  • Pseudo-random functions
  • Homework 1 due
  • Pseudo-random functions II
  • Security Reduction
4 2015-01-27
  • Security Reduction
  • Modes of Opeartion
  • Symmetric key Encryption
  • Symmetric Key Encryption II
5 2015-02-03
  • Symmetric Key Encryption III
  • INC-CCA-Security
  • Hash Functions
  • Homework 2 Solution
  • Practice questions for midterm
  • 6 2015-02-10
    • Midterm, in class
    • Hash Function II
    • Homework 3 due
    7 2015-02-17
    • Message Authentication Scheme
    • Authenticated Encryption
    • Lecture by John Retterermoore
    8 2015-02-24
    • Message Authentication II
    • Homework 4 due
    • Computational Number Theory
    9 2015-03-03
    • Computational Number Theory II
    • Public Key Encryption and El Gamal
    10 2015-03-10
    • Public Key Encryption and RSA
    • Homework 5 due
    • Review for Final
    11 2015-03-18
    • Final 7:30-9:30pm