Topics in Cryptography
G22.3033010 Fall 2002
Instructor: Victor Shoup

Phone: (212) 9983511

Office: 511 WWH
Lectures: Mondays, 57pm, 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 publickey cryptography.
Course topics
include (1) basics of computational number theory for cryptography,
(2) identification protocols,
(3) digital signatures, (4) publickey 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 SHA1?)
would be helpful.
Problem Sets
Other Reading Material
 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.
[postscript version]
[pdf version]
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 GuillouQuisquater 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 FiatShamir Heuristic, Schnorr's signature scheme,
the GuillouQuisquater signature scheme.

The CramerShoup signature scheme.
Part 4: Publickey encryption

Motivation, notions of security,
hybrid encryption/key encapsulation.

Simple RSA encryption, ElGamal encryption.

The CramerShoup encryption scheme.
Part 5: Additional topics
 To be determined (session key exchange?).