# G22.3033-010 Fall 2002

Instructor: Victor Shoup

• Phone: (212) 998-3511
• Office: 511 WWH

Lectures: Mondays, 5-7pm, 813 WWH

Text: Handbook of Applied Cryptography, by Menezes, van Oorscot, and Vanstone. Available on line.

Note that the lectures will not really follow the text at all. The text is intended mainly as a useful reference.

Grading: There will be three or four problem sets, and a term paper.

Course description:

The course is a seminar on topics in cryptography, with an emphasis on public-key cryptography. Course topics include (1) basics of computational number theory for cryptography, (2) identification protocols, (3) digital signatures, (4) public-key encryption, and (5) additional selected topics as time permits.

The course will focus on practical cryptographic schemes, but with an emphasis mathematically rigorous definitions and proofs of security.

The course is intended for graduate students interested in cryptography research. Although the course is meant to be as self contained as possible, familiarity with the rudiments of abstract algebra (what are groups and rings?), probability theory (what is conditional probability?), computational complexity theory (what is polynomial time?), and cryptography (what are DES and SHA-1?) would be helpful.

## Problem Sets

• A Primer on Algebra and Number Theory for Computer Scientists
These are some notes I've prepared to introduce and/or review some basic concepts in algebra and number theory that will be useful in this course.

## Course Outline (tentative)

### Part 1: Basics of computational number theory for cryptography

• Euclid's algorithm, modular exponentiation.
• Primality testing.
• The discrete logarithm and factoring problems.

### Part 2: Identification protocols

• Motivation, notions of security, Schnorr's identification scheme.
• The Guillou-Quisquater identification scheme.
• Security against active attacks, some zero knowledge.

### Part 3: Digital signatures

• Motivation, notions of security, message digest functions, full domain hash RSA signatures.
• The Fiat-Shamir Heuristic, Schnorr's signature scheme, the Guillou-Quisquater signature scheme.
• The Cramer-Shoup signature scheme.

### Part 4: Public-key encryption

• Motivation, notions of security, hybrid encryption/key encapsulation.
• Simple RSA encryption, ElGamal encryption.
• The Cramer-Shoup encryption scheme.