A1-Beveled.gif

CSCI 476, Fall 2017
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 402 or by appointment;
Email : shanghua[@]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.

Lectures

10:00-11:50am Monday and Wednesday, in room KAP 138  

Grades


10%: Participation
35%: Problem sets/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/21
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/23
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/28
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  
4
08/30
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/04
Labor Day (No Class)    
6
09/06
Perfectly-Secret Private-Key Encryption
      Information and Probability
Chapter 2  
7
09/11
Computational Approach to Security and Cryptography
Complexity Theory Basics
Randomness vs Pseudorandomness
Chapter 3.1, 3.2, 3.3  
8
9/13
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/18
RSA
      Number Theoretic Basics: Chinese Remainder Theorem
Chapter 10.4, Chapter 7, Chapter 11.1, and Chapter 11.5, Chapter 8  
10
9/20
RSA
      Number Theoretic Basics
Chapter 10.4 and Chapter 8, Chapter 11.5  
11
09/25
Rabin Encryption Scheme

Probabilistic Encryption

Chapter 13.5 and Chapter 13.4  
12
09/27
Diffie-Hellman Key Exchange Chapter 10  
13
10/02
Discrete Logarithms and El Gamal Encryption Scheme Chapter 11.4.1  
14
10/04
Pseudorandom Generation: Blum-Micali Construction
Number Theory Basics
Chapters 7.4-7.8 and Chapter 8 Chapter 5
15
10/09
Professor Kevin Knight's guest lecture

Cryptanalysis, NLP, and Statistical Learning

   
16
10/11
At KAP159: Professor Ming-Deh Huang's guest lecture

quantum cryptography: I

(I) News on quantum satellite Reuter 6/16/2017 China's quantum satellite makes breakthrough in secure communications https://www.reuters.com/article/us-china-space-satellite-idUSKBN1970SY Science 6/15/2017 Chinabture/PRL_67_661_Ekert.pdf EPR paper http://www.drchinese.com/David/EPR.pdf Bell Theorem (1) Original paper http://www.drchinese.com/David/Bell_Compact.pdf (2) Explanation http://drchinese.com/David/Bell_Theorem_Easy_Math.htm Quantum computation https://people.eecs.berkeley.edu/~christos/classics/Deutsch_quantum_theory.pdf (III) Wiki links: https://en.wikipedia.org/wiki/Quantum_computing https://en.wikipedia.org/wiki/Schr%C3%B6dinger%27s_cat https://en.wikipedia.org/wiki/Quantum_key_distribution https://en.wikipedia.org/wiki/Quantum_entanglement  
17
10/16
At KAP159: Professor Ming-Deh Huang's guest lecture

quantum cryptography: II

(I) News on quantum satellite Reuter 6/16/2017 China's quantum satellite makes breakthrough in secure communications https://www.reuters.com/article/us-china-space-satellite-idUSKBN1970SY Science 6/15/2017 Chinabture/PRL_67_661_Ekert.pdf EPR paper http://www.drchinese.com/David/EPR.pdf Bell Theorem (1) Original paper http://www.drchinese.com/David/Bell_Compact.pdf (2) Explanation http://drchinese.com/David/Bell_Theorem_Easy_Math.htm Quantum computation https://people.eecs.berkeley.edu/~christos/classics/Deutsch_quantum_theory.pdf (III) Wiki links: https://en.wikipedia.org/wiki/Quantum_computing https://en.wikipedia.org/wiki/Schr%C3%B6dinger%27s_cat https://en.wikipedia.org/wiki/Quantum_key_distribution https://en.wikipedia.org/wiki/Quantum_entanglement  
18
10/18
TBA

   
19
10/23
Indistinguishability and unpredicatability
Blum-Blum-Shub Pseudorandom generator
Chapters 7.4-7.8 and Chapter 8 Chapter 5
20
10/25
One Way and trapdoor functions, hardcore bits Chapter 7.1-7.3  
21
10/30

Intereactive and Zero Knowledge Proofs

Hangouts Hangouts
22
11/01
Zero Knowledge Proofs Hangouts  
23
11/06
Applications of Zero Knowledge Proofs: Multiparty Computation Hangouts  
24
11/08
Presentation:    
25
11/13
Presentation:
   
26
11/15
Presentation:    
27
11/20
Presentation:    
28
11/22
Thanksgiving (No Class)    
29
11/27
Presentation:    
30
11/29
Privacy and Security