### CS456/CS656 Cryptography

Spring 2001

**Instructor**: Christino Tamon

**Lecture**: Science Center 344 MWF 10am

**Office hours**: Science Center 373 MW 9-10am, 11-noon F 9-10am

**Pre-requisites**: MA211 or MA346, good programming skills and/or mathematical curiosity.

**Syllabus**:
Cryptography is the study of secure communication over insecure channels.
We will study the basic methods and concepts in theoretical cryptography
along with their applications. Concepts such as one-way functions and
trapdoor permutations (functions that are easy to compute but computationally
hard to invert), pseudorandom sequence generators (devices that produces
sequences that are computationally random), public-key cryptosystems
(secure systems that require no secret agreement), one-way hash functions
(tools to authenticate messages and to verify data integrity), digital
signatures (mechanisms for signing documents), and zero-knowledge proofs
(convincing a party of a fact without revealing its proof).
Most of the topics require background in number theory and probability theory.
The first part of the course will be spent on developing the necessary background
in these areas, mainly number theory. The second part of the course is spent on
the applications of these to building cryptographic tools.

**Grading scheme**
- Assignments and Quizzes 40%
- Midterm 20%
- Final exam 40%

**Texts**: [main][recommended]
- Schneier.
**Applied Cryptography**. John Wiley and Sons, Second edition, 1996.
- Bach and Shallit.
**Algorithmic Number Theory**. Cambridge University Press, 1996.
- Cormen, Leiserson, and Rivest.
**An Introduction to Algorithms**. MIT Press. (highly recommended)

### Assignments

- Cryptogram. Out: 01/12/01. Due: 01/19/01.

### Tentative Outline

- General framework of a cryptographic system:
Alice, Bob, and Eve. One-time XOR pad (unconditionally secure).
Problems with reusing the XOR pad. Types of attacks on cryptosystems:
ciphertext-only, known-plaintext, chosen-plaintext, adaptive chosen-plaintext,
chosen-ciphertext.

- The Rivest-Shamir-Adleman Public-Key CryptoSystem:
- Number Theory (Chapter 33 of Cormen, Leiserson, and Rivest's text).
- Assumptions and weaknesses of RSA:
deterministic property. multiplicative property.
hardness of FACTORING and computing the Euler function.

- A Probabilistic Public-Key CryptoSystem (Goldwasser-Micali):
- Number-theoretic background: quadratic residues, Blum integers.
computing square roots modulo a Blum integer. Legendre and Jacobi symbols.
- Assumptions and inefficiencies:
hardness of the Quadratic Residuosity Problem. sending 1-bit messages
as large random
*pseudosquares*.
- Security: semantically secure.

- A Pseudorandom Bit Generator (Blum-Blum-Shub):
- Universal tests: concept defined by Blum, Micali, and Yao.
- Assumptions: hardness of extracting square roots modulo Blum integers.
- Period and security

- More efficient probabilistic PKCS (Blum-Goldwasser):
- An improvement on the Goldwasser-Micali cryptosystem based on a
one-time pad using the BBS pseudorandom generator.
- Number-theoretic background: principal square roots modulo
Blum integers. the squaring function is a permutation over the quadratic
residues.

- Recent PKCS (Cramer-Shoup):
- Improvement on RSA: resistant against adaptive chosen ciphertext attack.
- Based on the assumed hardness Diffie-Hellman decision problem: a modified
El Gamal system.
- Practical and provably secure (Rackoff-Simon definition).

Citation: Ronald Cramer and Victor Shoup. A
practical public-key cryptosystem provably secure against chosen ciphertext
attack. Advances in Cryptology: Proceedings of CRYPTO'98.

- Zero Knowledge Proofs:
- Interactive proofs: completeness, soundness and zero-knowledge properties.
- Simple protocol: Quadratic Residues [Goldwasser-Micali-Rackoff]
- Identification scheme [Feige-Fiat-Shamir].

- Other topics:
- Cryptographic hashing.
- Coin flipping protocols.
- Bit commitment.
- Secret sharing.
- Cryptography in practice: DES, etc.