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. The course will look at concepts such as one-way functions and trapdoor permutations (functions that are easy to compute but computationally hard to invert), pseudorandom 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 an undeniable fact without revealing its proof).

Most of these 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.

*An alternative underlying theme of the course is the rise and "fall" of
the RSA cryptographic system. Theoretical properties and improvements of the RSA
system will be discussed in detail. Then a discussion of Shor's quantum
algorithm for Factoring will be described. Finally, a brief look at simple
quantum cryptography will be given.*

**TEXT**

Johannes Buchmann, "Introduction to Cryptography," 2nd
edition, Springer (2004)

*Recommended*:

- Victor Shoup, "A Computational Introduction to Number Theory and Algebra," Cambridge University Press (2005); link.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford
Stein, "Introduction to Algorithms," 2nd edition, The MIT Press (2001)
*(on reserve)*; - Bruce Schneier, "Applied Cryptography," 2nd edition, John Wiley & Sons
(1986)
*(on reserve)*

The objective of this course is to learn fundamental issues and important algorithms involved in the field of cryptography.

The specific outcomes are as follows:

- Knowledge of some secret-key cryptographic systems.
- Knowledge of important ideas in public-key cryptographic systems.
- Knowledge of basic ideas in number theory that are relevant to cryptography.
- Knowledge of various cryptographic protocols for implementing different types of communication that requires secrecy and protection.
- Knowledge of modern programming languages with support for cryptographic applications.

Although attendance is not mandatory, students are responsible for all course materials covered in lectures and any exams given during class periods. Students that need to make up missing course work must provide the required Clarkson official exempt form. All students must submit their own work; the exchange of ideas are encouraged but ultimately the submitted work must be the student's own. Please refer to the Clarkson University Regulations for more guidelines on academic integrity and related matters.

- General framework of a cryptographic system:

Classical one-time XOR pad (unconditionally secure). Problems with reusing the XOR pad. Secret-key vs Public-key systems. Types of attacks on cryptosystems: ciphertext-only, known-plaintext, chosen-plaintext, adaptive chosen-plaintext, chosen-ciphertext.

- The rise of the Rivest-Shamir-Adleman
(RSA) public-key cryptographic system
(PKCS):
- Background on Number Theory. Extended Euclid (Aryabhata's Pulverizer),
Chinese Remainder Theorem, Euler-Fermat Theorem, Miller-Rabin
fast probabilistic primality testing; proof of correctness + Carmichael
numbers. Recent result on primality testing: PRIMES in P.
Dan Boneh's course at Stanford University: number theory handout(s).

The PKCS standard for RSA.

Emerging ISO standard for PKCS.

RSA Challenge numbers.Assumptions and weaknesses of RSA: deterministic and multiplicative properties; Hardness of FACTORING; computing the Euler Totient function. Pollard's rho method method.

- A probabilistic PKCS of Goldwasser-Micali:

Quadratic residues, Blum integers; Hardness of computing MODULAR SQUARE ROOTS over a Blum integer. Legendre and Jacobi symbols; Hardness of the QUADRATIC RESIDUOSITY problem; Semantically secure.A more efficient probabilistic PKCS of Blum-Goldwasser:

A secure pseudo-random bit generator (PRBG) (Blum-Blum-Shub). One-time pad*public-key*system via the BBS generator; Principal square roots modulo Blum integers; Squaring is a permutation over the quadratic residues.

- Alternatives to RSA:

Diffie-Hellman key exchange protocol. El Gamal discrete-logarithm based public-key cryptosystem. Pollard's rho method for discrete logarithms.

*Miscellany*:*Coin flipping protocols*(Blum-Rabin); Bit commitment; Oblivious transfer (Rabin);*Cryptographic hashing*(Chaum-van Heijst-Pfitzmann);*Zero Knowledge Proofs and Identification Schemes*(Fiat-Shamir). Continued fractions and the Euclidean algorithm; Design of iterative binary extended Euclidean algorithm (Stein's method); Period of the Blum-Blum-Shub generator; The cyclic theorem for multiplicative groups modulo primes; Infinity proofs for primes: Euclid's proof, of special forms 4k+3 or 4k+1 (Dirichlet's theorem), safe primes; Computing square roots modulo any prime.

- Background on Number Theory. Extended Euclid (Aryabhata's Pulverizer),
Chinese Remainder Theorem, Euler-Fermat Theorem, Miller-Rabin
fast probabilistic primality testing; proof of correctness + Carmichael
numbers. Recent result on primality testing: PRIMES in P.
- The "fall" of the RSA cryptosystem
- Fast Fourier Transform and polynomial multiplication (Chapter 30 of Cormen et al's book).
- Quantum information and computation: basics (see Stan Gudder, "Quantum Computation", The American Mathematical Monthly, Volume 110, No. 3, March 2003, pages 181-201).
- The quantum factoring (prize-winning) algorithm of Peter Shor (see also Gudder's article above). John Watrous's QFT notes at MSRI.