Cryptography Reading List

TODOs

Signatures

• Ring
• blind
• threshold

ZK

• IOPs
  • HyperPlonk
  • Spartan memory-checking PCS
  • SuperSpartan
  • binius
    • binius-basefold
    • Understanding Binius, Part II
  • Polymath: Groth16 Is Not The Limit
  • Scribe: Low-memory SNARKs via Read-Write Streaming
  • Field-Agnostic SNARKs from Expand-Accumulate Codes
  • Blaze: Fast SNARKs from Interleaved RAA Codes
• folding
  • mangrove
  • mova
  • lova
  • HyperNova
  • Protostar
  • Protogalaxy
  • NeutronNova
  • MicroNova: Folding-based arguments with efficient (on-chain) verification
  • Twist and Shout: Faster memory checking arguments via one-hot addressing and increments
  • [ ]
  • Nebula
  • stackproofs
  • Albert Garreta and Ignacio Manzur, “FLI: Folding Lookup Instances”
  • KiloNova: Non-Uniform PCD with Zero-Knowledge Property from Generic Folding Schemes
  • LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems
  • Proof-Carrying Data from Multi-folding Schemes
  • One-Shot Native Proofs of Non-Native Operations in Incrementally Verifiable Computations
  • Proof-Carrying Data without Succinct Arguments
• lookups
  • logUp
  • Lasso
  • Lookup Arguments: Improvements, Extensions and Applications to Zero-Knowledge Decision Trees
  • Efficient KZG-based Univariate Sum-check and Lookup Argument
  • Natively Compatible Super-Efficient Lookup Arguments and How to Apply Them
  • FLIP-and-prove R1CS
• accumulation
  • Proofs for Deep Thought: Accumulation for large memories and deterministic computations
  • Accumulation without Homomorphism
• zkVMs
  • Jolt
    • https://www.youtube.com/watch?v=aEiHLORcDq4
    • https://www.youtube.com/watch?v=iDcXj9Vx3zY
  • Proving CPU Executions in Small Space: twist&shout with Jolt good + square root pcs is enough and simpler to implement + sumcheck can be streaming prove to prevent recursion (harder to reason with security and implementation)
  • Cairo – a Turing-complete STARK-friendly CPU architecture
• STARK/FRI
  • FRI
  • STIR
  • WHIR
  • Circle Starks
  • DEEP Commitments and Their Applications
• binius
  • binius-FRI, binius-basefold
  • Polylogarithmic Proofs for Multilinears over Binary Towers
  • Proximity Testing with Logarithmic Randomness
  • [ ]
• Sumcheck
  • More Optimizations to Sum-Check Proving
  • The Sum-Check Protocol over Fields of Small Characteristic
  • Constraint-Packing and the Sum-Check Protocol over Binary Tower Fields
  • Time-Optimal Interactive Proofs for Circuit Evaluation
  • Some Improvements for the PIOP for ZeroCheck
  • A Note on Efficient Computation of the Multilinear Extension
• Hashing
  • Skyscraper: Fast Hashing on Big Primes
• Misc
  • Khatam: Reducing the Communication Complexity of Code-Based SNARKs
  • ==How to Prove False Statements: Practical Attacks on Fiat-Shamir==
  • Zombie: Middleboxes that Don’t Snoop
    • Zero-Knowledge Middleboxes
  • Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs
    • Practical Proofs of Parsing for Context-free Grammars: also deliver competitive performance. In the non-interactive setting, proving the correct parsing of a ≈1KB string takes 24 seconds, even for grammars with 210 production rules. In the interactive setting the same proof takes just 1.6 seconds.

PCS

• Zeromorph
• Basefold
• HyperKZG
• Arc
• DewTwo
• KZH-Fold: Accountable Voting from Sublinear Accumulation
• DeepFold: Efficient Multilinear Polynomial Commitment from Reed-Solomon Code and Its Application to Zero-knowledge Proofs

Lattices

• Polynomial Commitments from Lattices: Post-Quantum Security, Fast Verification and Transparent Setup
• SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions
• Concretely Efficient Lattice-based Polynomial Commitment from Standard Assumptions
• Greyhound: Fast Polynomial Commitments from Lattices
• [ ]

Lattice

• RoK, Paper, SISsors – Toolkit for Lattice-based Succinct Arguments
• The LaZer Library: Lattice-Based Zero Knowledge and Succinct Proofs for Quantum-Safe Privacy
• A Survey of Polynomial Multiplications for Lattice-Based Cryptosystems
• [ ]

MPC

• Awesome MPC
• Jamie-Cui/awesome-secure-computation
• Large-Scale MPC: Scaling Private Iris Code Uniqueness Checks to Millions of Users
• OLE
• https://pascholl.github.io/download/BIU22-vole-1.pdf
• QuietOT: Lightweight Oblivious Transfer with a Public-Key Setup
• • read about OPRF and how it relates to:
    • PAKE
    • PSI
    • PIR
    • Keyword search

FHE

PETs

• Awesome PETs

PIR/PSI

Function Encryption/Witness encryption

• A Witness Encryption Construction over KZG-Committed Data
• Witness Encryption and its Applications
• Notes on Extractable Witness Encryption for KZG Commitments and Efficient Laconic OT

iO

• “Can We Obfuscate Programs?”, Boaz Barak
• “Theory and Practice of Program Obfuscation”

PQC

• read about quantum algorithms: start with Grover’s and Shor’s algorithm

Quantum Cryptography

Signatures

• lamport signatures
• Ring signatures
• Threshold signatures

---

• key derivation
  • https://en.wikipedia.org/wiki/Argon2
  • password based key derivation
• public key cryptosystem
  • micali-goldwasser
• OWF
• TLSN
• MPC
  • OT
    • 1-n
    • k-n
  • MPZ
  • SFE
  • Threshold cryptography
  • BMR protocol
  • Yao’s GC
  • BGW SFE
  • 2pc ecdsa
• LPN problem
• more secure random number generator
• prime number generator
• https://github.com/kimwalisch/primesieve/blob/master/doc/ALGORITHMS.md

Books/Courses

• PAZK
• “Building Cryptographic Proofs from Hash Functions”, Alessandro Chiesa and Eylon Yogev
• Summer School: Foundations and Frontiers of Probabilistic Proofs (Course A)
• Summer School: Foundations and Frontiers of Probabilistic Proofs (Course B)
• Spring 2019 - Probabilistically Checkable and Interactive Proof Systems (Alessandro Chiesa)