A1-Beveled.gif

CSCI 476, Fall 2021
Cryptography - Secure Communication & Computation

 Course Info:

 


Course descriptions and objectives

This course features a rigorous introduction to modern Cryptography -- a field that conducts mathematical & algorithmic studies of concepts, methods, and tools for protecting information in computer and communication systems. The course will focus on:

  • information-theoretic and computational views of security, privacy, and knowledge
  • fundamental cryptographic primitives (public-key encryption, digital signatures, pseudo-random number generation, and key agreement, etc)
  • basic protocols to guarantee confidentiality and authenticity of data and computation (secret sharing, homomorphic encryption, interactive and zero- knowledge proofs, and multi-party secure computation, digital money, etc)
  • computational complexity requirements in cryptography and practical implementation of cryptographic algorithms/protocols
We will also cover the relevant number theory and complexity theory. Students in the class are expected to have a reasonable degree of mathematical sophistication, and to be familiar with the basic notions of algorithms and data structures, discrete mathematics, and probability.

Prerequisites: CSCI 270 or permission of the instructor. If you have doubts about meeting these prerequisites, please contact the instructor.


Instructor

Professor Shang-Hua Teng
Office hours: by appointment;
Email: shanghua[@]usc.edu

TA

Joshua Palmer
Office hours: by appointment;
Email: jhpalmer@usc.edu

Textbook

Introduction to Modern Cryptography -- Second Edition
Jonathan Katz and Yehuda Lindell, Chapman & Hall/CRC Cryptography and Network Security Series

The class will also cover additional material drawn from research papers as well as other books in Theoretical Computer Science. Particularly:
A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup

Lectures

10:00-11:50am Monday and Wednesday, in room GFS 223  

In-Person Classroom Mask Policy

The University mask policy (based on the current CDC and LA County recommendations) will be strictly implemented in the classroom: At all times, everyone must have a mask properly covering their nose and mouth. During the two-hour lecture, we will have two regular breaks for students to go outside the building to drink water and have some fresh air.  

Grades
40%: Assignments
30%: Presentations/Participation
30%: Term paper

Exams

 

Homeworks

 

Integrity

Plagiarism and other anti-intellectual behavior will be dealt with severely. This includes the possibility of failing the course or being expelled from the University. 

 

Course Outline (subject to changes)

Lec#
Date
 Topic and/or Event Required Reading "Fun" Research Reading
1
08/23
 Class organization:


      data, information, and knowledge
      communication and computation
      How to model information, knowledge, security, and privacy
      Perfect Information Security vs Computational Security
      P vs NP
      Symmetric ciphers vs Public-Key Encryption
      Indistinguishability and unpredicatability
      Randomization and Interactive Proofs
      Languages, NLP, ML

Chapters 1-3
Search on the Web. For example:
      "google P NP"
      "google RSA"
      "google Zero Knowledge Proof"
      "google MAC"
      "google Digital signature"
      "google Homomorphic Encryption"
      "google Differential privacy"
      "google Network Security" 		Chapter 1.3
2
08/25
 Shamir's Secret Sharing Scheme: An Example of Perfect Security

Linear Algebra and Number Theory Basic

Handout, Shamir's CACM paper and Chapter 13.3 and Chapter 8 Chapter 1.1
3
08/30
 Secret Sharing II: A general Scheme
      Access Control
      Monotone Formula
      Two Basic Primitives
      general scheme Continue discussion of (perfect) information security 		Handout: Benaloh-Leichter, Generalized Secret Sharing and Monotone Functions Quantum Secret Sharing
Efficient Multi-Party Quantum Secret Sharing Schemes
4
09/01
 Classic Framework of Secure Communication -- The Setting of Private-Key Encryption
      Key generation
      Encryption/Decryption

Cryptanalysis
      Types of Attacks

Chapter 1.2, 1.4  
5
09/06
 Labor Day (No Class)    
6
09/18
 Perfectly-Secret Private-Key Encryption
      Information and Probability 		Chapter 2  
7
09/13
 Computational Approach to Security and Cryptography
Complexity Theory Basics
Randomness vs Pseudorandomness 		Chapter 3.1, 3.2, 3.3  
8
9/15
 Modern Framework of Secure Communication
      Public-key encryption
      Chosen Plaintext Attacks
      Number Theory Basics 		Chapters, 10.1. 10.2, and Chapter 7, Chapter 8  
9
9/20
 RSA
      Number Theoretic Basics: Chinese Remainder Theorem 		Chapter 10.4, Chapter 7, Chapter 11.1, and Chapter 11.5, Chapter 8  
10
9/22
 RSA
      Number Theoretic Basics 		Chapter 10.4 and Chapter 8, Chapter 11.5  
11
09/27
 Rabin Encryption Scheme

Probabilistic Encryption

Chapter 13.5 and Chapter 13.4  
12
09/29
 Diffie-Hellman Key Exchange Chapter 10  
13
10/04
 Discrete Logarithms and El Gamal Encryption Scheme Chapter 11.4.1  
14
10/06
 Pseudorandom Generation: Blum-Micali Construction
Number Theory Basics 		Chapters 7.4-7.8 and Chapter 8 Chapter 5
15
10/11
 Pseudorandom number generation    
16
10/13
 Pseudorandom number generation    
17
10/18
 Indistinguishability and unpredicatability
Blum-Blum-Shub Pseudorandom generator 		Chapters 7.4-7.8 and Chapter 8 Chapter 5
18
10/20
 One Way and trapdoor functions, hardcore bits Chapter 7.1-7.3  
19
10/25

Intereactive and Zero Knowledge Proofs

Hangouts Hangouts
20
10/27
 Zero Knowledge Proofs Hangouts  
21
11/01
 Applications of Zero Knowledge Proofs: Multiparty Computation Hangouts  
22
11/03
 Presentation:    
23
11/08
 Presentation

   
24
11/10
 Presentation:    
25
11/15
 Presentation:
   
26
11/17
 Presentation:    
27
11/22
 Presentation:    
28
11/24
 Thanksgiving (No Class)    
29
11/29
 Presentation:    
30
12/01
 Presentation