Most hash libraries treat hash functions as opaque blobs. You put data in, you get bits out, and that's the end of the story. Algebraic Hashing takes a different approach: it exposes the mathematical structure underneath, so you can compose hash functions like algebraic expressions. And because this is C++20 with concepts and templates, the composition resolves entirely at compile time. Zero runtime overhead.
The observation
Hash functions form an abelian group under XOR:
-
Closure:
h1 XOR h2is still a valid hash function -
Associativity:
(h1 XOR h2) XOR h3 = h1 XOR (h2 XOR h3) - Identity: XOR with zero
- Inverses: each hash is its own inverse under XOR
This is a clean algebraic structure, and it's the foundation for everything that follows.
What you can do with it
Compile-time composition. Using C++20 concepts and template metaprogramming:
auto composed = fnv1a<> ^ sha256<>;
auto hash = composed("data"); // Zero runtime overhead
All composition resolves at compile time. No virtual dispatch, no function pointers.
Provable properties. XOR composition preserves uniform distribution (under independence), avalanche effect, and collision resistance for cryptographic hashes. These aren't just empirical observations. They follow from the group structure.
Universal interface. Works with any hash function: non-cryptographic (FNV-1a), perfect (FKS), or cryptographic (SHA-256). The algebra doesn't care about the implementation details.
Practical uses
-
Domain separation:
hash_user ^ hash_timestampprevents collision attacks across domains - Perfect hashing: FKS two-level scheme with pluggable base hash functions
- Composite keys: hash multiple fields independently, then XOR
- Type-based hashing: different hash functions for different types, composed generically
Connection to oblivious computing
This work shares DNA with my oblivious computing research. The common thread is making mathematical structure explicit in the type system. Just as Bernoulli types enforce privacy invariants algebraically, algebraic hashing enforces compositional invariants through group theory. Same philosophy, different domain.
The library is header-only C++20 with zero-cost abstractions via concepts.
