Lecture 30

Assignment 7 (due Wednesday December 7 at 5 PM) and the solutions to Assignment 5 posted.

OT and Secure Computation

Lecture 29

Poker over the telephone. Overview of Secure Computation results.

Lecture 28

Secure Computation Examples

Coin Flipping, Yao's Millionaire Problem, Poker

Lecture 27

Private Information Retrieval

2 databases n bits from Alice, 4 databases n^1/2 bits, 1 database n^1/2 bits using quadratic residues

Gasarch webpage and survey

Lecture 26

Assignment 6 (due Wed Nov 30) and Assignment 4 solutions posted.

Shamir Secret Sharing, Homomorphic Encryption

Lecture 25

Assignment 3 solutions posted.

Quantum Key Distribution

Lecture 24

Shor's Quantum Factoring Algorithm

Lecture 23

Zero-Knowledge Sudoku
Bit Commitment

Lecture 22

Assignment 5 posted due Friday, November 18.

Bitcoin

Original Paper, Transactions, Blocks

Lecture 21

Digital Cash

Lecture 20

Digital Signatures, Collision-Resistant Hash Functions, El Gamal Scheme

Sections 4.6.1, 12.3.2, 12.4

Lecture 19

El-Gamal Encryption, Digital Signatures, Textbook RSA signatures
Sections 10.5, 12.1-12.3.1

Lecture 18

Assignment 4 posted.

RSA and El Gamal Sections 10.4-10.5

Lecture 17

Assignment 2 solutions posted.

Intel's New Random-Number Generator

Problems with "Textbook RSA" Section 10.4.1

Lecture 16

Lecture by Arefin Huq

* Definition and discussion of CDH and DDH (from 7.3.2)
* Choosing a Random Group Element (B.2.4)
* Finding a Generator of a Cyclic Group (B.3)
* Baby-Step/Giant Step Algorithm (8.2.1)
* overview of Pohlig-Hellman Algorithm (8.2.2)

Lecture 15

Some typos in problem 2 of assignment 3 have been fixed.

Hybrid Encryption, Section 10.3

Lecture 14

Lecturer: Arefin Huq

7.1.3 (Groups), 7.3.1 (Cyclic Groups and Generators), and the discrete logarithm experiment (7.3.2 up to Definition 7.59).

Lecture 13

Assignment 3 has been posted and is due Friday, October 28.

Public-Key Encryptions, Chosen-Plaintext Attacks and Multiple Message Encryptions
Textbook 10.1-10.2

Lecture 12

Factoring and RSA
Textbook 7.2.3 and 7.2.4

Lecture 11

Chinese Remainder and Primality Testing
Sections 7.1.5, 7.2.2

Lecture 10

Assignment 1 solutions posted.

Chosen Ciphertext Attacks Section 3.7
Introduction to Public Key Crypto
Math Background Section 7.1.4

Lecture 9

Assignment 2 is posted and due Wednesday October 19. Assignment was updated at 4 PM on October 10.

Constructing CPA-secure encryption schemes from pseudorandom functions
Sections 3.6.1-3.6.2

Lecture 8

Indistinguishable encryptions in the presence of an eavesdropper from a pseudorandom generator.
Sections 3.4.1-3.4.2
Chosen Plaintext Attacks
Section 3.5

Lecture 7

Lecture by Arefin Huq
Modular Arithmetic and Exponentiation

Chapter 7 through Section 7.1.2 and Appendix B through Section B.2.3

Lecture 6

Pseudorandom generators
Textbook Section 3.3

Upcoming Seminars
Tuesday Craig Mundie (Microsoft Research Chief) Converging Worlds: The New Era of Computing
Thursday Frontiers in Computer Science Symposium

Lecture 5

Implications of  indistinguishable encryptions in the presence of an eavesdropper.
Textbook Section 3.2.2

Lecture 4

Instructions for finding Assignment 1 are on the assignments page. Due Friday October 7th.

Formal definition of indistinguishable encryptions in the presence of an eavesdropper. Textbook section 3.1-3.2.1.

Lecture 3

Advanced Encryption Standard (AES)

Wikipedia Pages: AES, S-Box, Key Schedule

AES Animations

Lecture 2

Perfectly-Secret Encryption and One-Time Pads.

Textbook: Chapter 2

Lecture 1

Introduction of class, overview of non-modern cryptography and basic principles of modern crypto.

Textbook Chapter 1

Complexity Vidcast - Bill's Enigma

Course Information

EECS 395/495-0-21: Introduction to Cryptography

Fall 2011

Lecturer: Lance Fortnow

Grader: Arefin Huq

Lectures: MWF 1:00-1:50 in Tech LG66

For undergraduate CS majors this course can be used for either the Theory or Security depth requirement.

Description:

This course will give a broad overview of cryptographic techniques with an emphasis on modern tools based on prime numbers. We discuss many basic protocols from classical tools to DES, RSA and discrete logarithms and applications such as digital signatures, secure protocols, secret sharing, secure computation and zero-knowledge proofs. As time permits we will explore connections between cryptography, coding theory and quantum mechanics.

This course is designed for advanced undergraduates and graduate students. There are no official prerequisites but math knowledge of the level of Discrete Math (EECS 310) will be assumed. There will be no programming in the course.

Textbook: Modern Cryptography by Katz and Lindell. Errata