CS456/CS656 Cryptography
Spring 2002


Instructor: Christino Tamon
Lecture: Science Center 346 MWF 2pm
Office hours: Science Center 373 MW 8-10am, 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 Texts: [main][recommended]

Other recommended references


Assignments


Tentative Outline

  1. 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.
  2. The RSA Public-Key CryptoSystem and its derivatives
  3. 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).