A1-Beveled.gif

CSCI 476, Fall 2014
Cryptography - Secure Communication & Computation

=================================================

What's new?

 =================================================

 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 4:00-5:00 pm or by appointment;
Email : shanghua[@]usc.edu

TA/Grader

No TA assigned

Grader: Joe Bebel (bebel[@]usc.edu)  

Textbook

Introduction to Modern Cryptography: Principles and Protocols
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.

Lectures

10:00-11:20am Monday and Wednesday, in room VHE 217.  

Grades
10%: Participation
35%: Problem sets/Small quizzes
25%: Class 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/25
 Class organization:


      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

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/27
 Shamir's Secret Sharing Scheme: An Example of Perfect Security

Linear Algebra and Number Theory Basic

Handout, Shamir's CACM paper and Chapter 7 Chapter 1.1
3
09/01
 Labor Day (No Class)    
4
09/03
 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  
5
09/08
 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/10
 Perfectly-Secret Private-Key Encryption
      Information and Probability 		Chapter 2  
7
09/15
 Computational Approach to Security and Cryptography
Complexity Theory Basics
Randomness vs Pseudorandomness 		Chapter 3.1, 3.2, 3.3  
8
9/17
 Modern Framework of Secure Communication
      Public-key encryption
      Chosen Plaintext Attacks
      Number Theory Basics 		Chapters, 10.1. 10.2, and Chapter 7  
9
9/22
 RSA
      Number Theoretic Basics: Chinese Remainder Theorem 		Chapter 10.4 and Chapter 7  
10
9/24
 RSA
      Number Theoretic Basics 		Chapter 10.4 and Chapter 7  
11
09/29
 Rabin Encryption Scheme Chapter 11.2  
12
10/01
 Probabilistic Encryption Chapter 11.1  
13
10/06
 Pseudorandom generators and its use in symmetric ciphers Chapters 6.4-6.8 Chapter 5
14
10/08
 Pseudorandom Generation: Blum-Micali Construction
Number Theory Basics 		Chapters 6.4-6.8 and Chapter 7 Chapter 5
15
10/13
 Indistinguishability and unpredicatability
Blum-Blum-Shub Pseudorandom generator 		Chapters 6.4-6.8 and Chapter 7 Chapter 5
16
10/15
 Diffie-Hellman Key Exchange Chapter 9  
17
10/20
 Discrete Logarithms and El Gamal Encryption Scheme Chapter 10.5  
18
10/22
 Professor Kevin Knight's guest lecture

Cryptanalysis, NLP, and Statistical Learning

   
19
10/27
 One Way and trapdoor functions, hardcore bits Chapter 6.1-6.3  
20
10/29
 Digital Signatures, Message Authentication Codes (MAC), Hashing functions Chapters 4.1-4.6 and Chapter 12  
21
11/03
 Presentation: Barret Zoph

Intereactive and Zero Knowledge Proofs

Hangouts Hangouts
22
11/05
 Zero Knowledge Proofs Hangouts<  
23
11/10
 Applications of Zero Knowledge Proofs: Multiparty Computation Hangouts  
24
11/12
 Presentation: Phillip Lee
Presentation: Patrick Bradshaw and Tobias Lee

Digital Money

   
25
11/17
 Presentation: Jake Low
Presentation: Alex Bogart
Presentation: Ju Young Lee
   
26
11/19
 Presentation: Vikrant Singhal
Presentation: Shijie Xu
Presentation: Ju Young Lee (if conflict previously) 		   
27
11/24
 Presentation: Ruyan Chen and Thais Kagohara
Presentation: Ben Mayeux 		   
28
11/26
 Thanksgiving (No Class)    
29
12/01
 Working on Term Paper    
30
12/03
 Working on Term Paper