CS456/CS556 Cryptography

CS456/CS556 Cryptography (Spring 2024)

Pre-requisites: CS142 (CS344 highly recommended), MA211 or MA346. Good programming skills and/or mathematical curiosity.
Instructor: Christino Tamon
Lecture: TR 8:00-9:15 (SN212)
Office hours: TR 11:00-14:00 (SC373).

SYLLABUS
Cryptography is the study of secure communication over insecure channels. We will study the basic methods and concepts in cryptography along with their applications. The course will look at well-known modern cryptographic systems such as RSA, Diffie-Hellman, and elliptic curve cryptography.

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. The second part of the course is spent on the applications of these to building cryptographic tools.

An underlying theme of this course is the rise and "fall" of the RSA 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 quantum cryptography will be given.

GRADING: Assignments and Quizzes (40%), Midterm (20%), Final Exam (40%)

TEXT: W. Trappe, L. Washington, Introduction to Cryptography with Coding Theory, 3rd edition, Pearson, 2020.

OBJECTIVES/OUTCOMES:
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.

REQUIREMENTS/POLICIES:

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.

Schedule (updated regularly)

Secret-key systems: One-time pad. Unconditional security.
Public-key system: RSA (sample). Modular exponentiation (encryption and decryption). Random prime generation. Pairs of complementary keys. ElGamal (sample). Elliptic Curve ElGamal (sample). Quadratic Residue (sample). Lattice cryptography (GGH system).
Number theoretic tools: primes, modular arithmetic, division algorithm, Euclid's theorems (abundance of primes, recursive algorithm for GCD), Aryabhata's Pulverizer, Chinese Remainder Theorem, Fermat's Little Theorem (Euler's generalization).
Quantum cryptography and algorithms: BB84 key exchange protocol, Shor's algorithm (Deutsch-Josza, Bernstein-Vazirani, Simon).
Reference: S. Gudder, "Quantum computation", The American Mathematical Monthly, 2003.

Optional Notes (based on notes for a course taught at Harvey Mudd)

0: One-time Pad
1: Shannon's Theory
2: Basic Number Theory
3: RSA PKCS
4: ElGamal PKCS
5: Elliptic Curves
6: PKCS Based on Quadratic Residues
7: Miscellaneous Protocols
8: DES & AES
9: Quantum Ideas

Schedule (tentative)

Jan 9	Jan 11 One-time pad: shared random string symmetric, secret-key. Unconditionally secure. Reading: Chapters 2 and 4.
Jan 16 RSA: the protocol asymmetric, public-key. Computationally secure. Reading: Chapter 9.	Jan 18 RSA: basic number theory. Theorem (Euclid) there are infinitely many primes. Euclid's GCD (recursive) algorithm (is this parallelizable?). Reading: Chapter 3.
Jan 23 RSA: basic number theory. Extended Euclidean algorithm (Pulverizer of Aryabhata): recursive vs iterative (space-efficient). Reading: Chapter 3.	Jan 25 RSA: basic number theory. Modular arithmetic. Inverses modulo prime. Reading: Chapter 3.
Jan 30 RSA: Miller-Rabin primality testing. Fermat's Little Theorem. Extension: Euler-Fermat's theorem. Reading: Chapter 3.	Feb 1 RSA: Miller-Rabin primality testing. Modular exponentiation: fast recursive algorithm (iterative?). Nontrivial square roots of unity. Reading: Chapter 9, Section 3.
Feb 6 RSA: correctness (wrong proof via Euler-Fermat). Chinese Remainder Theorem (correct proof): parallel decryption. Exercise: worksheet. Reading: Chapters 3 and 9.	Feb 8 RSA: weaknesses and attacks. Reading: Chapters 9 and 14 (Section 2).
Feb 13 Discrete Logarithm: Diffie-Hellman. Reading: Chapter 10.	Feb 15 ElGamal: probabilistic public-key. Sample problem. Reading: Chapter 10.
Feb 20 ElGamal: Elliptic Curves. Sample problem. Reading: Chapter 21.	Feb 22 Short break.
Feb 27 Beyond RSA: Rabin cryptosystem. Modular square root (is equivalent to Factoring). Quadratic residues: Legendre and Jacobi symbols. Euler's criterion. Reference: notes by Angluin. Reading: Chapter 3.	Feb 29 Goldwasser-Micali cryptosystem. Semantic security. Blum integers. Magical properties: primes congruent to 3 mod 4. Reading: Chapter 3.
Mar 5 Blum-Goldwasser cryptosystem. Computational one-time pad. Blum-Blum-Shub pseudorandom bit generator. Reading: Chapter 3. sample.	Mar 7 Protocol: Zero-knowledge proofs (Goldwasser-Micali-Rackoff). Fiat-Shamir's Quadratic Residue protocol. Reading: Tompa.
Mar 12 Protocols: coin tossing, oblivious transfer, bit commitment. Yao's millionaiers problem. Secret sharing. Exercises: sample (sol)	Mar 14 Cryptographic hashing: birthday attack. DLOG-based: Chaum-van Heijst-Pfitzmann.
Mar 19 Spring break.	Mar 21 Spring break.
Mar 26 Block cipher: Modes of encryption: ECB, CBC, OFB, CFB.	Mar 28 Block cipher: DES. Feistel cipher.
Apr 2 Block cipher: AES. Polynomials. Finite Fields. Pulverizer over polynomials.	Apr 4 Block cipher: AES.
Apr 9 Quantum cryptography: basic quantum information.	Apr 11 Quantum cryptography: quantum key distribution (QKD): Bennett-Brassard (BB84).
Apr 16 Post-quantum: Shor algorithm: basic ideas.	Apr 18 Shor's algorithm: Quantum Fourier Transform.
Apr 23 Lattice cryptography: LLL algorithm. Source: notes (Peikert).	Apr 25 Lattice cryptography: LLL algorithm.

ASSIGNMENTS

Assignment 0 (polyalphabetic substitution)
Assignment 1 . (RSA-4096)
Assignment 2 . (SaferRSA-2048) Whose clue is it?
Assignment 3 . (ElGamal [halfmask,cipher])
Assignment 4 . (Elliptic-Curve-ElGamal [cipher,halfmask])

Topics

Real-world: SSL, [Georgiev et al] (attack); SSH; GNU PGP, PGPi, MIT site, Zimmerman; Logjam attack.
Secure Hash Algorithm (SHA): RFC, Schneier; SHA-3 (Keccak). Hashing: [Halevi et al];
RSA: PKCS#11; [Brumley-Boneh] (timing attacks); [Bleichenbacher] (attack on PKCS#1).
Elliptic curves: [Lauter]; [Koblitz et al] (survey); Sage support; J2ME;
Lattice cryptography: [Nguyen-Regev] (attack on signature scheme), [Nguyen]; talk by Peikert; Quanta article.
Homomorphic encryption: [Gentry] (PhD thesis), [Lauter et al] (practicality), [Gentry-Halevi], github.
Zero Knowledge Proofs: [Feige-Fiat-Shamir]; [Blum et al.] (non-interactive ZKP).
Quantum Cryptography: BB84; ACM Survey (Bruss et al); Shor-Preskill;
Bell nonlocality: [Buhrman-Cleve-Massar-deWolf]; [Hanggi-Renner-Wolf]
Byzantine agreement: [Arora] (Rabin's algorithm); [Lamport] (leaderless).
Miscellany: McEliece cryptosystem (quantum-resistant). Merkle-Hellman cryptosystem (precursor to Diffie-Hellman). Authentication protocols.
More: Mental Poker. Identity-based encryption.

RESOURCES/LINKS:

Textbooks: Shoup. Mermin. Boneh and Shoup.
Online reference: A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.
Crypto programming support: Java, NTL, Python.
Crypto archive: arXiv.
Miscellany: blunders; cartoon guide to AES; ACM Turing award; Quantum comix. IBMQ.
A few crypto sources:
1. S. Gudder, "Quantum computation", The American Mathematical Monthly, March ,2003.
2. D. Coppersmith, "Cryptography", IBM J. Res. Develop., vol. 44, no. 1/2, 2000.
3. S. Landau, "Standing the test of time: The Data Encryption Standard", Notices of the AMS, vol. 47, no. 3, pp341-349, 2000.
4. D. Angluin, "Lecture Notes on the Complexity of Some Problems in Number Theory", TR #243, 1982, Yale.
5. C. Pomerance, "A Tale of Two Sieves," Notices of the AMS, vol. 12, 1996.
6. J. Quisquater et al., "How to Explain Zero-Knowledge Protocols to Your Children," Advances in Cryptology, pp. 628-631, 1989.
7. D. Boneh, "Twenty Years of Attack on the RSA Cryptosystem," Notices of the AMS, vol. 46, no. 2, 203-213, 1999.
8. M. Agarwal, N. Kayal, N. Saxena, "PRIMES in P" (appeared in Annals of Mathematics).
9. K. Lauter, "The advantages of elliptic curve cryptography for wireless security," IEEE Wireless Communications, vol. 11, no. 1, 62-67, 2004.
10. Elliptic curves: Sage examples. NIST .