Foundations of Cryptography

Here is the list of topics discussed in the MIT course "Foundations of Cryptography" (MIT 6.5620/6.875/18.425) during the Fall 2022 semester:

Module 1:

• Lecture 1: Introduction to cryptography, secure communication, Shannon's definitions of perfect secrecy, the one-time pad construction, and Shannon's lower bound.
• Lecture 2: Computational security, pseudorandom generators (PRG), and stateful secret-key encryption.
• Lecture 3: The Hybrid Argument, PRG length extension, pseudorandom functions (PRF), and PRFs imply secret-key encryption.
• Lecture 4: Formal definition of PRF security, the Goldreich-Goldwasser-Micali (GGM) PRF construction, and IND-CPA secure encryption.
• Lecture 5: Identification protocols, authentication, message-authentication codes (MAC), and chosen ciphertext secure symmetric key encryption.
• Lecture 6: One-way functions, hard core bits, PRG, and the Goldreich-Levin theorem.
• Lecture 7: Continued discussion on the Goldreich-Levin theorem and a TCS perspective on GL theorem: local list decoding.

Module 2:

• Lecture 8: Merkle's key exchange protocol, public-key encryption, group theory, and number theory.
• Lecture 9: Discrete Log Assumption, Diffie-Hellman key exchange, and Diffie-Hellman/El Gamal encryption.
• Lecture 10: Trapdoor functions, RSA, QRA, Goldwasser-Micali, and homomorphism.
• Lecture 11: Digital signatures, Lamport's One-time Signature Scheme.
• Lecture 12: Collision-resistant hash functions, many-time, stateful signature schemes, and Naor-Yung construction.

Module 3:

• Lecture 14: Zero knowledge proofs I: definitions and examples.
• Lecture 15: Zero knowledge proofs II: Zero Knowledge Proofs for all of NP.
• Lecture 16: Succinct (Zero Knowledge) Argument Systems, Merkle Trees, Probabilistically Checkable Proofs, and Kilian's Protocol.

Module 5:

• Lecture 18: Lattices, Learning with Errors (LWE), LWE-based Cryptography, and Fully Homomorphic Encryption.
• Lecture 19: Fully Homomorphic Encryption continued: The Bootstrapping Theorem, and Circular Security.

Module 6:

• Lecture 21: Oblivious Transfer and Private Information Retrieval.
• Lecture 22: Secure Two-Party Computation and the Goldreich-Micali-Wigderson Protocol.
• Lecture 23: Secret-Sharing and Secure Multiparty Computation.
• Lecture 24: Program Obfuscation and Applications.
• Lecture 25: Yao's Garbled Circuits.
• Lecture 26: Quantum Cryptography.
• Lecture 27: Grand Challenges in Cryptography and Crypto AMA with Vinod and the TAs.

Please note that this is a summary of the topics covered and may not include every subtopic or detail discussed within each lecture.

Graduate Cryptography

Here is the list of topics discussed in the MIT/UC Berkeley course "Graduate Cryptography" (MIT 6.875 / Berkeley CS 276):

• Lecture 0: Introduction
• Lecture 1: Shannon, perfect security, and the one-time pad
• Lecture 2: The computational adversary, definition of computational security, pseudo-random generators, and symmetric encryption
• Lecture 3: One-way functions, hard core bits, and the Goldreich-Levin theorem
• Lecture 4: Pseudo-random generators: definition, construction, and properties
• Lecture 5: Pseudo-random functions: definition, construction, and properties
• Lecture 6: Pseudo-random permutations, AES, and symmetric key encryption
• Lecture 7: Number theory 1: discrete log, MSB, and QR
• Lecture 8: Number theory 2: factoring and RSA
• Lecture 9: Public key encryption I: construction from RSA and Quadratic Residuosity
• Lecture 10: Public key encryption II: construction from Diffie-Hellman and Learning with Errors
• Lecture 11: Digital signatures and MACs I
• Lecture 12: Digital signatures and MACs II
• Lecture 12b: Merkle Trees and Certificate Transparency
• Lecture 13: Proof of Work, consensus, cryptographic transactions, Bitcoin application
• Lecture 14: Zero knowledge I: definitions and examples
• Lecture 15: Zero knowledge II: NP in ZK
• Lecture 16: Non-interactive zero knowledge proofs (NIZK)
• Lecture 17: Chosen ciphertext attack (CCA)
• Lecture 18: Zcash: privacy-preserving cryptocurrency with zero-knowledge proofs
• Lecture 19: Specialized homomorphic encryption and applications
• Lecture 20: Lattices and Learning with Errors (LWE)
• Lecture 21: Fully homomorphic encryption
• Lecture 22: Private information retrieval (PIR) from FHE
• Lecture 23: Secret sharing
• Lecture 24: Garbled circuits and Yao's two-party computation protocol
• Lecture 25: GMW two-party computation
• Lecture 26: Practical machine learning with MPC (optional for Berkeley)

ZK Knowledge

1. Introduction and History of Zero-Knowledge Proofs

   • Knowledge Complexity of Interactive Proof Systems
   • How to prove all NP-statements in zero-knowledge
   • Practical solutions to identification and signature problems
   • Defining proofs of knowledge

2. Overview of Modern SNARK Constructions

   • Schwartz-Zippel Lemma
   • zk-SNARKs: A Gentle Introduction
   • Using ZK Proofs to Fight Disinformation
   • Zero Knowledge Canon

3. Libraries and Compilers to build ZKP

   • Circom Documentation
   • Arkworks Tutorial
   • ZoKrates Documentation
   • Efficient Constructions of ZKP

4. Interactive Proofs (IP)

   • Interactive Proofs and the Sum-Check Protocol
   • Chapters 3 and 4 of [Thaler]
   • Merkle Trees
   • Sum-Check-Based Polynomial IOPs for Circuit-SAT

5. Plonk Interactive Oracle Proofs (IOP)

   • Constant-Size Commitments to Polynomials and Their Applications
   • Feist-Khovratovich technique for computing KZG proofs fast
   • Dory: Efficient, Transparent arguments for Generalised Inner Products and Polynomial Commitments
   • PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge
   • HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates
   • PLONKish Arithmetization
   • Polynomial Commitments

6. Discrete-log-based Polynomial Commitments

   • A Zero-Knowledge Version of vSQL
   • Bulletproofs: Short Proofs for Confidential Transactions and More

7. ZKP based on Error-Correcting Codes

   • Ligero: Lightweight Sublinear Arguments Without a Trusted Setup
   • Orion: Zero Knowledge Proof with Linear Prover Time
   • Brakedown: Linear-time and post-quantum SNARKs for R1CS

8. Transparent ZKP

   • FRI Paper
   • Best Existing Soundness Analysis of FRI
   • Polynomial Commitments from FRI
   • Round-by-round Soundness, Fiat-Shamir, and Sum-check
   • Linear PCP

9. Linear Probabilistically Checkable Proofs (PCP)

   • Pinocchio
   • Succinct Non-Interactive Arguments via Linear Interactive Proofs
   • Groth16
   • Recursive SNARKs

10. Recursive SNARKs, Aggregation, and Accumulation

    • Recursive STARK Proofs
    • Incrementally Verifiable Computation via Incremental PCPs
    • Scalable Zero Knowledge via Cycles of Elliptic Curves
    • Nova
    • Proof-Carrying Data without Succinct Arguments
    • Folding Schemes with Selective Verification

11. Theoretical Foundations & Recent Theoretical Advancements

12. Overview of ZKP Applications & zkRollup and zkEVM

13. Building opcode compatible zk EVMs

14. Privacy-preserving Architectures

15. ZKP Applications & zkBridge, Trustless Bridge made Practical

16. More ZKP Applications

17. Formal Verification of ZKP

18. Hardware Acceleration of ZKP

This is from Zk-learning.org!

Elliptic Curves

Do this for the mathematical integrity.

From MIT, again.

1. Introduction to elliptic curves
2. The group law, Weierstrass and Edwards equations
3. Finite field arithmetic
4. Isogenies
5. Isogeny kernels and division polynomials
6. Endomorphism rings
7. Hasse's Theorem and point counting
8. Schoof's algorithm
9. Generic algorithms for the discrete logarithm problem
10. Index calculus, smooth numbers, factoring integers
11. Elliptic curve primality proving (ECPP)
12. Endomorphism algebras
13. Ordinary and supersingular curves
14. Elliptic curves over C (complex numbers)
15. Complex multiplication (CM)
16. The CM torsor
17. Riemann surfaces and modular curves
18. The modular equation
19. The Hilbert class polynomial
20. Ring class fields and the CM method
21. Isogeny volcanoes
22. The Weil pairing
23. Modular forms and L-functions
24. Fermat's last theorem

These topics cover various aspects of elliptic curves, including their algebraic properties, applications in cryptography, and connections to number theory and algebraic geometry.

A bird's view understanding is fine.

Mathematics

Number theory

1. Modular arithmetic: Understanding modular arithmetic is crucial for many cryptographic algorithms. Topics like congruences, modular inverses, Chinese remainder theorem, and Fermat's little theorem are fundamental.

2. Prime numbers and factorization: Prime numbers are essential for various cryptographic algorithms. Topics like prime factorization, primality testing, prime number generation, and the distribution of primes are important.

3. Discrete logarithm problem: The discrete logarithm problem forms the basis of several cryptographic systems. Understanding the concepts of discrete logarithms, the Diffie-Hellman key exchange, and elliptic curve cryptography is crucial.

4. Primality testing: Different primality testing algorithms, such as the Miller-Rabin test and AKS primality test, are used in cryptography. Understanding these algorithms and their computational complexity is important.

5. Cryptographic hash functions: Hash functions are widely used in cryptography. Topics like collision resistance, pre-image resistance, and the Merkle-Damgård construction are relevant.

6. Public-key cryptography: Familiarize yourself with concepts like RSA, ElGamal, elliptic curve cryptography (ECC), and their underlying number-theoretic properties.

7. Lattices: Lattice-based cryptography is a post-quantum cryptographic approach. Topics like lattice basis reduction (e.g., LLL algorithm), lattice-based encryption schemes (e.g., Learning With Errors), and lattice-based signature schemes are worth exploring.

8. Error-correcting codes: Error-correcting codes, such as Reed-Solomon codes and BCH codes, have applications in cryptography, particularly in code-based cryptography. Understanding their properties is beneficial.

Algebraic Structures

1. Groups: Groups are sets equipped with an operation that satisfies certain properties. In cryptography, groups are often used for key exchange protocols and in the construction of symmetric ciphers. Understanding group properties, such as closure, associativity, identity element, inverses, and the concept of group orders, is essential.

2. Rings: Rings are algebraic structures that consist of a set with two operations (addition and multiplication). In cryptography, rings are employed in various contexts, such as modular arithmetic and error-correcting codes. Understanding ring properties, including commutativity, associativity, distributivity, and the existence of additive and multiplicative identities, is important.

3. Fields: Fields are algebraic structures that extend the concept of rings by requiring that all non-zero elements have multiplicative inverses. Fields play a crucial role in many cryptographic algorithms, particularly in public-key cryptography, where concepts like modular arithmetic and finite fields are employed.

4. Finite Fields: Finite fields, also known as Galois fields, are fields with a finite number of elements. They are extensively used in cryptography, especially in elliptic curve cryptography (ECC) and certain public-key algorithms like the RSA and Diffie-Hellman protocols. Understanding finite field arithmetic, field extensions, irreducible polynomials, and the structure of finite fields is essential.

5. Vector Spaces: Vector spaces are algebraic structures that generalize the concepts of addition and scalar multiplication. In cryptography, vector spaces find applications in error-correcting codes, cryptographic hash functions, and certain encryption schemes. Understanding vector space properties, linear independence, basis, and dimension is relevant.

6. Boolean Algebra: Boolean algebra deals with binary variables and logical operations like AND, OR, and NOT. It forms the foundation of symmetric key cryptography, where bitwise operations and logical functions are employed. Understanding Boolean algebra, truth tables, Boolean functions, and their properties is important in designing and analyzing cryptographic algorithms.