A1-Beveled.gif

CSCI 476, Fall 2019
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: Monday 12:00 noon - 13:00 pm RTH 505 or by appointment;
Email : shanghua[@]usc.edu

TA

No TA assigned

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 111  

Grades


10%: Participation
35%: Problem sets/Reqired Reading/Class Discussions
25%: Presentations (could be done in group)
30%: Term paper (group + individual)

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/26
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/28
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
09/02
Labor Day (No Class)    
4
09/04
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
5
09/09
Classic Framework of Secure Communication -- The Setting of Private-Key Encryption
      Key generation
      Encryption/Decryption

Cryptanalysis
      Types of Attacks

Chapter 1.2, 1.4  
6
09/11
Perfectly-Secret Private-Key Encryption
      Information and Probability
Chapter 2  
7
09/16
Computational Approach to Security and Cryptography
Complexity Theory Basics
Randomness vs Pseudorandomness
Chapter 3.1, 3.2, 3.3  
8
9/18
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/23
RSA
      Number Theoretic Basics: Chinese Remainder Theorem
Chapter 10.4, Chapter 7, Chapter 11.1, and Chapter 11.5, Chapter 8  
10
9/25
RSA
      Number Theoretic Basics
Chapter 10.4 and Chapter 8, Chapter 11.5  
11
09/30
Rabin Encryption Scheme

Probabilistic Encryption

Chapter 13.5 and Chapter 13.4  
12
10/02
Diffie-Hellman Key Exchange Chapter 10  
13
10/07
Discrete Logarithms and El Gamal Encryption Scheme Chapter 11.4.1  
14
10/09
Pseudorandom Generation: Blum-Micali Construction
Number Theory Basics
Chapters 7.4-7.8 and Chapter 8 Chapter 5
15
10/14
Pseudorandom number generation    
16
10/16
At GFS 107: Professor Ming-Deh Huang's guest lecture    
17
10/21
Indistinguishability and unpredicatability
Blum-Blum-Shub Pseudorandom generator
Chapters 7.4-7.8 and Chapter 8 Chapter 5
18
10/23
One Way and trapdoor functions, hardcore bits Chapter 7.1-7.3  
19
10/28

Intereactive and Zero Knowledge Proofs

Hangouts Hangouts
20
10/30
Zero Knowledge Proofs Hangouts  
21
11/04
Applications of Zero Knowledge Proofs: Multiparty Computation Hangouts  
22
11/06
Presentation:    
23
11/11
At KAP159: Professor Ming-Deh Huang's guest lecture

   
24
11/13
Presentation:    
25
11/18
Presentation:
   
26
11/20
Presentation:    
27
11/25
Presentation:    
28
11/27
Thanksgiving (No Class)    
29
12/02
Presentation:    
30
12/04
Presentation