reading_list.md

f2chat Prerequisite Reading List

This document outlines the essential knowledge required to understand and contribute to f2chat. It is structured for a Computer Science undergraduate with a strong interest in cryptography and algebraic topology.

1. Cryptography Foundations

Before diving into FHE, you need a solid grasp of modern cryptography and ring theory.

• Modular Arithmetic & Ring Theory:

  • Concept: Understanding $\mathbb{Z}_q$ and polynomial rings $\mathbb{Z}_q[x]/(x^n+1)$.
  • Resource: A Book of Abstract Algebra (Charles C. Pinter)
    • Chapter 10: Cyclic Groups (Understanding $\mathbb{Z}_n$).
    • Chapter 17-19: Rings, Ideals, and Quotient Rings (Crucial for modular arithmetic).
    • Chapter 24: Rings of Polynomials (The structure of our ciphertexts).
    • Chapter 25: Factoring Polynomials (Irreducibility and $x^n+1$).
  • Why: FHE ciphertexts are polynomials in a specific ring structure.

• Lattice-Based Cryptography:

  • Concept: Learning with Errors (LWE) and Ring-LWE problems.
  • Resource: A Decade of Lattice Cryptography (Peikert) - Read sections 1 & 2 for high-level intuition.
  • Why: The security of BGV (the scheme we use) relies on the hardness of these problems.

• Fully Homomorphic Encryption (FHE):

  • Concept: Computing on encrypted data without decryption.
  • Resource: FHE for the rest of us (Microsoft Research)
  • Deep Dive: The BGV Scheme (Brakerski-Gentry-Vaikuntanathan) - Focus on the "Leveled FHE" concept.

2. The OpenFHE Library

We use OpenFHE as our cryptographic backend.

• Getting Started:

  • Resource: OpenFHE Getting Started Guide
  • Key Sections: Installation, "Your First OpenFHE Program".

• BGV in OpenFHE:

  • Resource: OpenFHE BGV Example
  • Why: This example mirrors how we initialize our FHEContext and perform basic operations.

3. Mathematical Framework (Sheaf & Wreath)

This is the unique theoretical core of f2chat.

• Sheaf Theory:

  • Concept: Local data consistency (patches) leading to global solutions.
  • Resource: Sheaf Theory for Undergraduates (Gallier) - Read the introduction and first chapter.
  • Intuition: Think of a "sheaf" as a way to glue local routing rules together to form a valid global route.

• Wreath Products:

  • Concept: A group construction that captures "position-dependent" symmetry (like a rubik's cube or a network with local structure).
  • Resource: Wreath Product (Wikipedia) - Focus on the "Group Action" definition.
  • Why: Our routing attention mechanism is a "Wreath-Sheaf" attention, meaning it respects these specific symmetries.

4. Engineering & Tooling

Practical skills needed to build and test the system.

• Bazel Build System:

  • Resource: Bazel Tutorial: C++
  • Why: We use Bazel for hermetic builds and dependency management.

• Modern C++ (C++17/20):

  • Resource: A Tour of C++ (Stroustrup)
  • Key Concepts: std::shared_ptr, std::vector, Templates, absl::StatusOr (from Abseil).

• Google Test (GTest):

  • Resource: GoogleTest Primer
  • Why: All our verification is done via unit and integration tests.