A corpus of my notes and articles on Cryptography, Networking and Formal methods
Link  Summary 

Primer to Cryptography  Introduction to the fundamental concepts of cryptography. 
Graduate Cryptography  Advanced topics in cryptography for higherlevel study. 
ZK Knowledge  Understanding ZeroKnowledge proofs and their applications. 
Elliptic Curves  Exploring the mathematics and applications of elliptic curves. 
Number Theory  Topics related to number theory and its cryptographic relevance. 
Complex Analysis and Algebraic Structures  Discussion on the role of complex analysis in cryptography. 
Application of formal methods  Using formal methods for cryptographic protocol analysis. 
Complexity Theory and Cryptography  The interplay between complexity theory and cryptographic constructions. 
Cryptoanalysis  Techniques for analyzing and breaking cryptographic schemes. 
Networking fundamentals  Basics of computer networking and communication protocols. 
Network Security  Measures to secure computer networks from threats and attacks. 
Solutions to Cryptopals  My solutions to the Cryptopals challenges. 
If something is incomplete, I'll try to finish it up ASAP. I'm tranferring 34 notebooks worth of notes first to digital text, formatting it with Markdown + LaTex and then finally posting them here, while dealing with build issues. It's a lot of fun (and this is not sarcastic). Sometimes I'll discover "Wait, this is all off" and other times I go "This could use a practical code example!", thus adding to the delay. The Python code to visualise the graphs and other such things are stored in the Github repo here (opens in a new tab).
Primer to Cryptography
Heavily inspired by MIT 6.5620/6.875/18.425 (opens in a new tab) Cryptography is essential for securing information in the digital world. This section covers the core concepts and constructions in cryptography.

Introduction to Cryptography and Perfect Secrecy  Overview of cryptography, its goals, and perfect secrecy as defined by Shannon. Understanding the foundations.

Computational Security and Pseudorandom Generators  Moving beyond perfect secrecy to computational security against bounded adversaries. Introducing pseudorandom generators.

Hybrid Argument and Pseudorandom Functions  Hybrid argument for proving computational indistinguishability. PRFs from PRGs.

GoldreichGoldwasserMicali PRF Construction and INDCPA Encryption  Constructing PRFs from PRGs. Using PRFs for INDCPA symmetric encryption.

MACs, and Chosen Ciphertext Secure Encryption  Authentication via identification protocols. Message authentication codes. INDCCA secure encryption.

GoldreichLevin Theorem  The GoldreichLevin theorem for finding hardcore bits.

TCS Perspective on GoldreichLevin Theorem and Local List Decoding  Theoretical computer science view of GoldreichLevin theorem. Connections to list decoding.

Merkle's Key Exchange and PublicKey Encryption  Key exchange from OWFs. Publickey encryption from key exchange.

Discrete Log Assumption and DiffieHellman Key Exchange  Discrete log assumption. DiffieHellman key exchange.

Trapdoor Functions, RSA, and Homomorphism  Trapdoor functions and RSA construction. Homomorphic encryption.

Digital Signatures and Lamport's Onetime Signature Scheme  Digital signatures. Lamport's onetime signature scheme.

Collisionresistant Hash Functions and NaorYung Construction  Collision resistance. NaorYung construction of CCA encryption from CRHFs.

Lattices, Learning with Errors (LWE), and LWEbased Cryptography  Introduction to lattices. Learning with errors problem. LWEbased crypto.

Fully Homomorphic Encryption and Bootstrapping Theorem  Fully homomorphic encryption. Bootstrapping theorem.

Oblivious Transfer and Private Information Retrieval  1outof2 OT. Private information retrieval.

Secure TwoParty Computation and GoldreichMicaliWigderson Protocol  Secure computation. GMW protocol.

Program Obfuscation and Applications  Program obfuscation. Applications.

Yao's Garbled Circuits  Yao's garbled circuits construction.

Quantum Cryptography  Introduction to quantum cryptography.
Graduate Cryptography
Advanced cryptography topics typically covered in graduate courses.

Overview of Number Theory: Discrete Log, MSB, and QR  Discrete log. Modular square roots. Quadratic residuosity. Factoring and RSA. The RSA trapdoor permutation.

Public Key Encryption I: Construction from RSA and Quadratic Residuosity  Publickey encryption from RSA and QR.

Public Key Encryption II: Construction from DiffieHellman and Learning with Errors  Publickey encryption from DH and LWE.

Digital Signatures and MACs I  Definition and constructions of digital signatures. Message authentication codes.

Digital Signatures and MACs II  More on digital signatures and MACs.

Merkle Trees and Certificate Transparency  Merkle trees. Certificate transparency.

Proof of Work, Consensus, Cryptographic Transactions, and Bitcoin  Proof of work. Distributed consensus. Bitcoin.

Zero Knowledge I: Definitions and Examples  Zero knowledge proofs. Basic definitions and examples.

Zero Knowledge II: NP in ZK  Zero knowledge for all of NP. ZK proof systems.

NonInteractive Zero Knowledge Proofs (NIZK)  Efficient noninteractive zero knowledge proofs.

Zcash: Privacypreserving Cryptocurrency with Zeroknowledge Proofs  Zcash and its use of NIZKs.

Specialized Homomorphic Encryption and Applications  Somewhat homomorphic encryption. Applications.

Fully Homomorphic Encryption  Fully homomorphic encryption.

Private Information Retrieval (PIR) from FHE  Constructing PIR schemes from FHE.

Secret Sharing  Secret sharing schemes.

Garbled Circuits and Yao's Twoparty Computation Protocol  Yao's garbled circuits. Secure twoparty computation.

GMW Twoparty Computation  The GMW protocol for secure twoparty computation.

Practical Machine Learning with MPC (optional for Berkeley)  Secure multiparty computation for machine learning.
ZK Knowledge
Zero knowledge proofs are revolutionizing blockchain technology. This section provides an indepth overview of modern ZKP constructions and applications. ˜

Introduction and History of ZeroKnowledge Proofs  Background and history of ZK proofs.

Overview of Modern SNARK Constructions  Highlevel overview of modern succinct noninteractive arguments of knowledge (SNARKs).

Practical ZK  SNARK vs STARK, practical examples: bulletproof, Plonk, Marlin. ZCash, Monero, ZK Rollups.

Libraries and Compilers to Build ZKP  Tools and libraries for building ZK proofs.

Interactive Proofs (IP) and Merkle Trees  Interactive proofs. Using Merkle trees in ZK systems.

Plonk Interactive Oracle Proofs (IOP)  The Plonk IOP construction and protocol.

Discretelogbased Polynomial Commitments  Polynomial commitments based on the discrete log.

ZKP Based on ErrorCorrecting Codes  Leveraging error correcting codes.

Transparent ZKP  Transparency in ZK proofs.

Killian's Protocol and Linear PCPs  Killian's protocol. Linear probabilistically checkable proofs (PCPs).

Linear Probabilistically Checkable Proofs (PCP)  Linear PCPs.

Recursive SNARKs, Aggregation, and Accumulation  Recursive proof composition. Proof aggregation and accumulation.

Theoretical Foundations & Recent Theoretical Advancements  Theoretical foundations and latest advancements.

Overview of ZKP Applications & zkRollup and zkEVM  ZK proof applications. zkRollup and zkEVM.

Building Opcode Compatible zk EVMs  Constructing EVMcompatible zk virtual machines.

Privacypreserving Architectures  Architectures leveraging ZK proofs for privacy.

More ZKP Applications  Additional applications of ZK proofs.

Formal Verification of ZKP  Formal verification of ZK systems.

Hardware Acceleration of ZKP  Hardware optimizations for ZK proofs.

Practicum: Exercises using Circom and SnarkJS  Handson exercises using Circom and SnarkJS.
Elliptic Curves
Elliptic curves are fundamental to modern cryptography. This section provides a deep dive into elliptic curve theory, construction, and applications.

Introduction to Elliptic Curves  Basic introduction to elliptic curves.

The Group Law, Weierstrass and Edwards Equations  Group law. Weierstrass and Edwards models.

Finite Field Arithmetic  Arithmetic in finite fields.

Isogenies and Division Polynomials  Isogenies. Division polynomials.

Endomorphism Rings  Endomorphism rings of elliptic curves.

Hasse's Theorem and Point Counting  Hasse's theorem. Point counting algorithms.

Schoof's Algorithm  Schoof's point counting algorithm.

Generic Algorithms for the Discrete Logarithm Problem  Algorithms for the ECDLP.

Index Calculus, Smooth Numbers, and Factoring Integers  Index calculus. Smooth numbers. Factorization algorithms.

Elliptic Curve Primality Proving (ECPP)  Using elliptic curves for probabilistic primality proving.

Endomorphism Algebras  Endomorphism algebras of elliptic curves.

Ordinary and Supersingular Curves  Ordinary vs supersingular curves.

Elliptic Curves over Complex Numbers (C)  Elliptic curves over the complex numbers.

Complex Multiplication (CM) and CM Torsor  Complex multiplication. CM torsors.

Riemann Surfaces and Modular Curves  Riemann surfaces. Modular curves.

The Modular Equation  The modular equation.

The Hilbert Class Polynomial  Hilbert class polynomials.

Ring Class Fields and the CM Method  Ring class fields. The CM method for constructing curves.

Isogeny Volcanoes  Isogeny volcanoes.

The Weil Pairing  The Weil pairing and its properties.

Modular Forms and Lfunctions  Modular forms. Lfunctions.

Fermat's Last Theorem  Using elliptic curves to prove Fermat's last theorem.
Number Theory

Modular Arithmetic  Modular arithmetic, groups, inverses. Important foundation.

Prime Numbers and Factorization  Primes, unique factorization. Important cryptographic assumptions.

Discrete Logarithm Problem  Discrete log problem, DiffieHellman. Core cryptographic hardness assumption.

Primality Testing  Testing primes and generating primes. Used in key generation.

Cryptographic Hash Functions  Hash functions, collision resistance. Essential cryptographic primitive.

PublicKey Cryptography  Public key encryption, signatures. enabled modern crypto.

ErrorCorrecting Codes  ECCs, decoding. Used in codebased crypto.
Algebraic Structures
 Lattices and fundamental domains  Lattices, fundamental domains, and Voronoi cells.
 Holomorphic functions and modular forms  Holomorphic functions, modular forms, and the modular group.
 Meromorphic functions and elliptic curves  Mero functions, elliptic curves, and the jinvariant.
 Primer to Elliptic Functions  Elliptic functions, Weierstrass P function, and the Weierstrass zeta function.
Understanding algebraic structures crucial for cryptography. Groups, Rings, Fields, Finite Fields, Vector Spaces, Boolean Algebra
Application of formal methods
Applcations via Coq

Formal foundations  This covers the core mathematical and logical foundations used in formal methods, including inductively defined data types, functions and relations specified recursively, mathematical induction and rewriting for proofs, operational semantics to formally define program meaning, and data abstraction techniques for organizing proofs about data representations.

Type systems  This explores how type systems can enable static verification of programs. Topics include lambda calculus as a model of computation, type soundness proofs showing type safety, and advanced type system features like subtyping and mutable references that increase expressiveness while preserving soundness.

Program logics  These logics support reasoning about imperative programs. Hoare logic offers formal verification based on pre and postconditions. Different embeddings of source programs enable different proof methods. Separation logic supports modular reasoning about pointermanipulating programs.

Concurrency models  Concurrency introduces new challenges for verification. Operational semantics can model concurrent behavior. Separation logic and relyguarantee reasoning enable modular proofs about shared state. Process calculi like picalculus provide highlevel languages for modeling and reasoning about messagepassing programs.

Key concepts  There are important highlevel concepts that apply across models and methods. Encoding choices have big impacts on proof complexity. Invariants are central to most proofs about stateful programs. Abstraction and modularity enable tackling large systems by breaking them into smaller pieces.

Applications to Cryptography  Covers writing some proofs for cryptographic constructions in Coq. Also discusses EasyCrypt.
Complexity Theory and Cryptography
Complexity theory is a branch of theoretical computer science that studies the resources required to solve computational problems. It provides a theoretical framework for understanding the efficiency of algorithms and the inherent difficulty of solving specific computational tasks. For cryptography, several elements of complexity theory are relevant and essential:

Computational Complexity Classes: Complexity theory defines classes of computational problems based on the amount of computational resources required to solve them. The most wellknown complexity classes are P (problems solvable in polynomial time) and NP (problems verifiable in polynomial time). Cryptographers often work with problems that are believed to be hard in the worstcase scenario (NPhard) or difficult to solve efficiently (NPcomplete). Understanding these complexity classes helps cryptographers analyze the security of cryptographic protocols and algorithms.

OneWay Functions: Oneway functions are central to many cryptographic constructions. These are functions that are easy to compute in one direction but computationally infeasible to invert in the other direction without specific additional information. Complexity theory provides the foundation for defining and studying the properties of oneway functions and their applications in cryptography, such as in public key cryptography.

Computational Intractability: Complexity theory investigates problems that are computationally intractable, meaning they cannot be solved efficiently by any known algorithm. This is closely related to the concept of hardness in cryptography. Cryptographers often rely on the assumption that certain problems are hard to solve, forming the basis for cryptographic protocols like factoring for RSA and discrete logarithms for DiffieHellman.

Reductions: Reductions are fundamental tools in complexity theory used to establish relationships between different problems. In cryptography, reductions are used to demonstrate that breaking one problem is equivalent to breaking another problem, thus providing evidence of the security of cryptographic constructions.

Randomized Complexity: Randomized algorithms and complexity classes like BPP (boundederror probabilistic polynomial time) are relevant in cryptography. They allow for probabilistic analysis and the construction of algorithms that may not be guaranteed to be correct every time, but they are correct with high probability. Randomized algorithms are employed in certain cryptographic protocols and algorithms to improve efficiency and security.

Interactive Proof Systems: Complexity theory explores interactive proof systems, where a prover tries to convince a verifier about the validity of a claim. These concepts underpin the study of zeroknowledge proofs, which are widely used in modern cryptographic protocols to prove knowledge of information without revealing that information.

Hardness Assumptions: Cryptographic security often relies on the assumption that certain computational problems are hard to solve. Complexity theory helps in understanding the strength of these hardness assumptions and their implications for the security of cryptographic schemes.
Cryptoanalysis
 Kerckhoffs' Principle: Security of a cryptographic system relies on the secrecy of the key, not the algorithm.
 Notions of Security: Assessing security in terms of confidentiality, integrity, authenticity, and more.
 Models of Attack: Different attack models, such as chosen plaintext, chosen ciphertext, etc.
 Targets of Attack: Analyzing weaknesses in block ciphers, stream ciphers, hash functions, key exchange protocols, etc.
 Theoretical Attacks vs. Practical Attacks: Distinguishing attacks based on mathematical principles from those considering realworld limitations.
 Lessons Learned from Classic Ciphers: Insights gained from historical ciphers like the Caesar cipher and Vigenère cipher.
 Cryptanalysis of Block Ciphers:
 MeetintheMiddle Attack & TMTO.
 Basic Differential Analysis.
 Basic Linear Analysis.
 WideTrail Strategy and AES.
 Integral Cryptanalysis.
 Truncated Differential Attack.
 Higher Order Differential Attack.
 Boomerang and Rectangle Attacks.
 Impossible Differential Attack.
 MultiDimensional Linear Attack.
 ZeroCorrelation Linear Attack.
 Division Property.
 DemirciSelcuk MitM Attack.
 Subspace Trail Cryptanalysis.
 More (Optional): Advanced cryptanalysis techniques and attacks.
 Cryptanalysis of Stream Ciphers:
 GuessandDetermine Attack on Stream Ciphers.
 TimeMemoryData Tradeoff Attack.
 Linear Distinguisher and Correlation Attacks.
 Cryptanalysis of Hash Functions:
 Birthday Attacks.
 MD and Sponge.
 Differential Cryptanalysis and Collision Attacks.
 MeetintheMiddle Preimage Attack
 ComputerAided Cryptanalysis:
 MILPbased Cryptanalysis.
 SATbased Cryptanalysis.
 Algebraic Cryptanalysis.
 Interpolation Attack.
 Cube Attacks and Higher Order Differential Attack.
 Linearization.
 MerkleHellman Knapsack
 DiffieHellman Key Exchange and MitM
 Discrete Log Algorithms:
 BabyStep GiantStep.
 Factoring Algorithms.
 Dixon's Algorithm.
 Quadratic Sieve.
 Quantum Algorithms
Networking fundamentals
Follows the CCNA guide (opens in a new tab).
 Network fundamentals (components, topology, cabling, TCP/IP)
 Network access (VLANs, spanning tree, wireless LANs)
 IP connectivity (routing protocols, first hop redundancy)
 IP services (DHCP, DNS, NAT, QoS)
 Security fundamentals (threats, access control, VPNs, wireless security)
 Automation and programmability (controllerbased networking, APIs, configuration management)
Network Security
(Follows CS558 by Prof. Kaptchuk ~ I was enrolled for his course in Spring '22 and was deeply inspired)
 Internet Infrastructure Protocols (eg. BGP, ARP, DNS)
 DDoS and Reflection Attacks
 TLS (eg. FREAK, Logjam, Drown, Heartbleed, Goto Fail, PKI infrastructure)
 Crypto Wars
 Tor (eg. Protocol obfuscation, Protocol tunneling)
 Proxying (eg. Domain Fronting and Encrypted SNI, Telex and Tapdance)
 Attacking Secure Messaging (eg. Padding oracles, iMessage attack)
 Signal Protocol (eg. Forward/Backward Secrecy, OTR, Sealed Sender Messaging, Private Information Retrieval)
 Private Computation  Trusted Execution Environments and MPC (Security Model, Attacks, Real Applications)
 Two Party Computation/Multiparty Computation (BU and BWWC, STORMY Tor measurement, End to End 2PC/MPC compilers)
Cryptopals
Set 1: Basics  Basics of cryptography and encoding. Set 2: Block crypto  Block ciphers and modes of operation. Set 3: Block & stream crypto Set 4: Stream crypto and randomness Set 5: DiffieHellman and friends) Set 6: RSA and DSA Set 7: Hashes Set 8: Abstract Algebra