Skip to main content

Cipher Maps: When Category Theory Meets Oblivious Computing

5 min read Updated:
oblivious computing category theory algebraic cipher types cipher maps functors type theory cryptography Bernoulli models research

What if we could compute on encrypted data while preserving algebraic structure? Not through expensive homomorphic encryption, but through a principled mathematical framework that unifies oblivious computing, Bernoulli types, and categorical abstractions?

That’s what my recent work on cipher maps and algebraic cipher types explores.

The Vision: Computing Without Seeing

Imagine you have a monoid (S, *, e) with some operation * and identity e. Now imagine computing on encrypted versions of elements from S while:

  • Preserving the monoidal structure
  • Hiding the actual values
  • Getting approximate but privacy-preserving results
  • Maintaining composability

This is what cipher functors enable.

Two Foundational Papers

1. Algebraic Cipher Types (algebraic-cipher-types)

The core idea: A cipher functor cA that lifts a monoid (S, *, e) into a cipher monoid (cA(S), ⊕, cA(e)).

Latent space:  (S, *, e)      -- the "real" monoid
                ↓ cA (cipher functor)
Cipher space:  (cA(S), ⊕, ê)  -- encrypted monoid

Key properties:

  • cA(x * y) ≈ cA(x) ⊕ cA(y) (structure preservation, up to approximation)
  • Operations on ciphers don’t reveal the underlying values
  • Composition of cipher operations mirrors composition in the base monoid

Why this matters: We get a type system for oblivious computing. Instead of ad-hoc encryption schemes, we have principled constructions that preserve algebraic structure.

Examples:

  • Encrypted counters: (ℕ, +, 0) lifts to oblivious count structures
  • Encrypted sets: (𝒫(U), ∪, ∅) lifts to hash-based oblivious sets (Bloom filters)
  • Encrypted multisets: (ℕᵁ, ⊕, 0̄) lifts to Count-Min sketches

2. Cipher Maps (cipher-maps)

This paper unifies three major threads:

  1. Algebraic cipher types (categorical foundations)
  2. Bernoulli types (statistical approximation theory)
  3. Oblivious function approximation (practical algorithms)

The synthesis: Cipher maps are morphisms in a category where:

  • Objects are cipher types (encrypted/oblivious data structures)
  • Morphisms preserve both algebraic structure AND statistical properties
  • Composition gives you principled ways to build complex oblivious computations

Key contribution: Oblivious Bernoulli maps

These are functions f : cA(S) → cA(T) that:

  • Operate on encrypted/oblivious inputs
  • Produce encrypted/oblivious outputs
  • Have provable error bounds (from Bernoulli type theory)
  • Preserve categorical structure (from cipher functors)

Practical result: You can now:

  1. Start with a regular function f : S → T
  2. Lift it to a cipher map cA(f) : cA(S) → cA(T)
  3. Get automatic privacy guarantees
  4. Get formal error bounds
  5. Compose multiple cipher maps while tracking error propagation

Why Category Theory?

You might ask: why all the abstract mathematics?

Answer: Category theory gives us composition for free.

Without it, every new oblivious algorithm is a one-off construction with custom security proofs. With cipher functors:

  • Functoriality: cA(f ∘ g) = cA(f) ∘ cA(g) — composition of secure operations is secure
  • Natural transformations: Generic ways to convert between different oblivious representations
  • Limits/colimits: Systematic construction of compound oblivious types
  • Monoidal structure: Parallel composition of oblivious computations

This isn’t just elegance—it’s practical abstraction that lets you build complex systems from verified components.

Connection to Hash-Based Oblivious Sets

The cipher-trapdoor-sets paper shows a concrete instantiation:

Hash-Based Oblivious Sets (HBOS) = cipher functor applied to (𝒫(U), ∪, ∅)

The construction:

  1. Start with the powerset monoid (sets with union)
  2. Apply the cipher functor with hash-based Bernoulli maps
  3. Get: Bloom filters with provable privacy guarantees
  4. Bonus: the categorical structure gives you set operations (union, intersection) for free

Novel contribution: Unlike traditional Bloom filters (just data structures), HBOS are oblivious types with:

  • Formal privacy semantics
  • Compositional error bounds
  • Type-safe operations
  • Integration with cipher maps for complex queries

Practical Applications

This framework enables several applications I’m actively developing:

1. Privacy-Preserving Databases

Use cipher maps to build database operators (join, project, select) that work on oblivious data while hiding access patterns.

2. Encrypted Analytics

Aggregation queries (SUM, COUNT, AVG) lift naturally to cipher maps over appropriate monoids.

3. Federated Learning

Gradient aggregation with oblivious types ensures differential privacy without trusted aggregators.

4. Secure Streaming

Process streams with cipher maps over streaming monoids—constant memory, provable privacy.

From Theory to Practice

The beauty of this framework: it’s implementable.

A cipher functor isn’t just mathematical abstraction—it’s a design pattern for building oblivious systems:

// Pseudocode sketch
template<typename T>
class CipherFunctor {
    using Cipher = ObliviousBernoulli<T>;

    Cipher lift(T value);
    T approximate_inverse(Cipher cipher);

    // Monoidal operation on ciphers
    Cipher combine(Cipher a, Cipher b);
};

I’m working on C++ implementations using modern template metaprogramming to make cipher types zero-cost abstractions.

Looking Forward

These papers open several research directions:

  1. Higher categories: What about functors between cipher categories?
  2. Dependent types: Can we encode privacy/accuracy trade-offs in the type system?
  3. Effect systems: Track information flow using cipher maps
  4. Compiler integration: Automatically lift regular code to oblivious versions

Why This Matters Now

We’re at an inflection point where:

  • Privacy regulations demand oblivious computing
  • Scale requires approximate algorithms
  • Complexity demands compositional abstractions

Cipher maps provide the mathematical foundation to build these systems correctly.

Instead of:

  • Ad-hoc crypto + hope
  • Custom privacy proofs for each algorithm
  • Non-compositional security guarantees

We get:

  • Principled constructions from category theory
  • Automatic privacy from functoriality
  • Compositional security from categorical structure

Related Papers:

This work synthesizes my research in oblivious computing, type theory, and cryptography into a unified framework. The mathematics is deep, but the payoff is practical: systematic construction of privacy-preserving systems with formal guarantees.

Related Posts

Discussion