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