What if you could compute on encrypted data while preserving algebraic structure? Not through expensive homomorphic encryption, but through a mathematical framework that unifies oblivious computing, Bernoulli types, and categorical abstractions.
That’s what cipher maps and algebraic cipher types are about.
Computing without seeing
Start with a monoid (S, *, e) with some operation * and identity e. Now compute on encrypted versions of elements from S while preserving the monoidal structure, hiding actual values, getting approximate but privacy-preserving results, and maintaining composability.
Cipher functors make this possible.
Two papers
1. Algebraic cipher types (paper)
A cipher functor cA lifts a monoid (S, *, e) into a cipher monoid (cA(S), +, cA(e)).
Latent space: (S, *, e) -- the "real" monoid
| cA (cipher functor)
v
Cipher space: (cA(S), +, e') -- encrypted monoid
Key properties:
cA(x * y) ~ cA(x) + cA(y)(structure preservation, up to approximation)- Operations on ciphers don’t reveal underlying values
- Composition of cipher operations mirrors composition in the base monoid
This gives you a type system for oblivious computing. Instead of ad-hoc encryption schemes, you get principled constructions that preserve algebraic structure.
Concrete examples:
- Encrypted counters:
(N, +, 0)lifts to oblivious count structures - Encrypted sets:
(P(U), union, empty)lifts to hash-based oblivious sets (Bloom filters) - Encrypted multisets: lifts to Count-Min sketches
2. Cipher maps (paper)
This paper unifies three threads:
- Algebraic cipher types (categorical foundations)
- Bernoulli types (statistical approximation theory)
- Oblivious function approximation (practical algorithms)
Cipher maps are morphisms in a category where objects are cipher types, morphisms preserve both algebraic structure and statistical properties, and composition gives you principled ways to build complex oblivious computations.
The key contribution is oblivious Bernoulli maps: functions f : cA(S) -> cA(T) that operate on encrypted inputs, produce encrypted outputs, have provable error bounds from Bernoulli type theory, and preserve categorical structure from cipher functors.
In practice, you can:
- Start with a regular function
f : S -> T - Lift it to a cipher map
cA(f) : cA(S) -> cA(T) - Get automatic privacy guarantees
- Get formal error bounds
- Compose multiple cipher maps while tracking error propagation
Why category theory
The natural question: why all the abstract machinery?
Category theory gives you 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 mathematical aesthetics. It’s practical abstraction that lets you build complex systems from verified components.
Hash-based oblivious sets
The boolean-algebra-trapdoor-sets paper shows a concrete instantiation.
Hash-Based Oblivious Sets (HBOS) = cipher functor applied to (P(U), union, empty).
The construction:
- Start with the powerset monoid (sets with union)
- Apply the cipher functor with hash-based Bernoulli maps
- Get Bloom filters with provable privacy guarantees
- The categorical structure gives you set operations (union, intersection) for free
Unlike traditional Bloom filters (just data structures), HBOS are oblivious types with formal privacy semantics, compositional error bounds, type-safe operations, and integration with cipher maps for complex queries.
Applications
This framework enables several things I’m working on:
Privacy-preserving databases: cipher maps for database operators (join, project, select) that work on oblivious data while hiding access patterns.
Encrypted analytics: aggregation queries (SUM, COUNT, AVG) lift naturally to cipher maps over appropriate monoids.
Federated learning: gradient aggregation with oblivious types ensures differential privacy without trusted aggregators.
Secure streaming: process streams with cipher maps over streaming monoids, constant memory, provable privacy.
Implementation
A cipher functor isn’t just 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.
What’s next
These papers open several research directions:
- Higher categories: what about functors between cipher categories?
- Dependent types: can we encode privacy/accuracy trade-offs in the type system?
- Effect systems: track information flow using cipher maps
- Compiler integration: automatically lift regular code to oblivious versions
Why now
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 plus hope, custom privacy proofs for each algorithm, and non-compositional security guarantees, you get principled constructions from category theory, automatic privacy from functoriality, and compositional security from categorical structure.
Papers:
- Algebraic Cipher Types
- Cipher Maps: Unified Framework
- Hash-Based Oblivious Sets
- Bernoulli Types Series
- Encrypted Search with Oblivious Types
This work synthesizes my research in oblivious computing, type theory, and cryptography. The mathematics is involved, but the payoff is practical: systematic construction of privacy-preserving systems with formal guarantees.
Discussion