Spring 2002

- Assignments and Quizzes 40%
- Midterm 20%
- Final exam 40%

- Bruce Schneier.
**Applied Cryptography**. 2nd edition. Wiley, 1996. - Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein.
**An Introduction to Algorithms**. 2nd edition. The MIT Press, 2001. (highly recommended)

**Other recommended references**

- David Bressoud
**Factorization and Primality Testing**. Springer-Verlag, 1989. - Jonathan Knudsen.
**Java Cryptography**. O'Reilly, 1998. (in ERC library) - Scott Oaks.
**Java Security**. O'Reilly, 1998. (in ERC library) - Simon Singh.
*The Code Book*. Anchor Books, 2000. - Julian Brown.
*The Quest for the Quantum Computer*. Touchstone, 2001.

- 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 RSA Public-Key CryptoSystem and its derivatives
- 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 secure PseudoRandom Bit Generator (Blum-Blum-Shub)

Universal tests: concept defined by M. Blum, S. Micali, and A.C-.C. Yao.

Assumptions: hardness of extracting square roots modulo Blum integers.

Period and security: connection to the Carmichael function. - A 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. - Zero Knowledge Proofs and Identification Schemes.

Interactive proofs: completeness, soundness and zero-knowledge properties (GMR). Simple protocol based on Quadratic Residues (Fiat-Shamir). Identification schemes (Schnorr).

- Other topics:

Cryptographic hashing (Chaum-van Heijst-Pfitzmann). Coin flipping protocols (Blum-Rabin). Bit commitment (PRBG-based) (classical and quantum). Secret sharing (Shamir). Cryptography in practice: DES and Feistel ciphers. Quantum algorithms and implications to Factoring (Shor).