Skip to main content

Algebraic Hashing: Composable Hash Functions Through XOR

2 min read Updated:
cryptography hash functions algebra C++ template metaprogramming

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 h2 is 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_timestamp prevents 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.

View the whitepaper | GitHub

Related Posts

Discussion