Trapdoor Computing
Computing on opaque encodings: the cipher map framework, its papers, and the monograph that unifies them.
The one-sentence version. Imagine a service that cannot read your queries and cannot read its own answers, yet still returns the right ones. Trapdoor computing is the paradigm that makes that precise. A trusted machine holds the encoder and decoder; an untrusted machine sees only total functions on opaque bit strings flowing through opaque lookup tables. It cannot tell a real query from filler, one encoding from another, or a correct result from noise.
The organizing object is the cipher map: a total function on bit strings that implements a trapdoor approximation of a hidden function. Four properties make it measurable rather than magical, totality, representation uniformity, correctness, and composability, and confidentiality here is measured (in the sense of quantitative information flow), not assumed negligible (in the sense of a cryptographic reduction). The privacy comes from one-way hashing and uniform representation, not from hiding access patterns: this is deliberately not ORAM, not fully homomorphic encryption, not garbled circuits.
The monograph: the center of gravity
Everything below is being drawn together into one book.
Trapdoor Computing: Computing on Opaque Encodings builds the cipher map abstraction from first principles, develops its algebra and type theory, characterizes its confidentiality at two scales, gives concrete constructions, and closes with the open problems that define the next program. Six parts:
- The Paradigm, the trusted/untrusted model and what trapdoor computing is not.
- The Cipher Map Abstraction, the four properties and the parameter tuple.
- Algebra and Types, Boolean algebra over trapdoor values, algebraic cipher types, orbit closure.
- Confidentiality, the marginal scale (a single map) and the compositional scale (chains of maps).
- Constructions, hash-based, GF(2)-linear, rekeying, and closures.
- Frontiers, the open problems that motivate what comes next.
The monograph is the synthesis. Each paper below is roughly a chapter’s worth of the argument; the book is where they become one coherent treatment instead of a stack of separate results. It is in active development.
The papers
The program is a family of papers, each a self-contained result the monograph consolidates. Three already carry minted DOIs; the rest are under submission or in preparation.
Core
| Paper | What it establishes | Status |
|---|---|---|
| Cipher Maps: Total Functions as Trapdoor Approximations | The abstraction itself: the four properties, the parameter tuple, batch and online construction, and the space-accuracy duality. The hub the rest build on. | Manuscript, targeting PoPETs |
| The Entropy Ratio: Quantitative Confidentiality | The confidentiality theory. Two scales that do not reduce to each other; the headline is a sharp, matching-bounds rate for joint recovery under composition that no per-map parameter can lower. DOI | Targeting CSF |
| Algebraic Cipher Types | The type theory: product and sum types over trapdoors, the sum-type impossibility, and orbit-closure bounds against an active adversary. DOI | Deposited |
| Codec-Controlled Retrieval | A GF(2)-linear ribbon/XOR construction whose non-member output channel is turned into a designable, frequency-hiding distribution at zero per-query cost. | Under review, ACM TOPS |
In preparation
| Paper | What it adds |
|---|---|
| Cipher Rekeying (DOI) | Re-keying a deployed system through cipher closures, without ever decoding. |
| Cipher Closures | Cipher data structures and the code-data duality, spun out of rekeying. |
| Cipher Program Construction | Realizing whole programs as compositions of cipher maps. |
| Adaptive Trapdoor | Maintaining confidentiality as the query distribution drifts. |
Folded in
Boolean Algebra over Trapdoor Sets was the original construction. Its two load-bearing ideas, the generalized Boolean algebra and the deterministic single-hash baseline, are now folded into Cipher Maps and Algebraic Cipher Types, and the standalone is archived. It is still the cleanest entry point to the intuition.
What I would like to publish
The near-term plan is three venues and a book. The Entropy Ratio goes to CSF: its matching-bounds theorem is the lowest-variance result to defend at a foundations venue. Codec-Controlled Retrieval is under review at ACM TOPS. Cipher Maps, the hub, targets PoPETs. And the monograph is the long game, the place where a reader who wants the whole picture (rather than one theorem) can get it.
If you are deciding whether the work is worth your time: start with the series page for the paradigm, read The Entropy Ratio for the sharpest single result, and ask me about the monograph for the synthesis.
Posts and notes
The development is chronicled in a series of posts, the authentic 2023-2024
foundations and the commentary since. This hub tracks them automatically, by
the trapdoor-computing series and tag, so the list grows as the work does:
- Entropy Maps · February 2024Entropy maps use prefix-free hash codes to approximate functions without storing the domain, achieving information-theoretic space bounds with controllable error.
- Entropy Maps · February 2024Entropy maps use prefix-free hash codes to approximate functions without storing the domain, achieving information-theoretic space bounds with controllable error.
- Perfect Hashing: Space Bounds, Entropy, and Cryptographic Security · February 2024Space bounds, entropy requirements, and cryptographic security properties of perfect hash functions.
- A Boolean Algebra Over Trapdoors · June 2023A Boolean algebra framework over trapdoors for cryptographic operations. Introduces a homomorphism from powerset Boolean algebra to n-bit strings via cryptographic hash functions, enabling secure …
- Noisy Turing Machines: Noisy Logic Gates · June 2023Analyzing how Bernoulli Boolean types propagate through logic circuits, with correctness probabilities for noisy AND gates and interval arithmetic for composed circuits.
- The Bernoulli Model: A Probabilistic Framework for Data Structures and Types · June 2023The Bernoulli Model is a framework for reasoning about probabilistic data structures by treating noisy outputs as Bernoulli-distributed approximations of latent values, from Booleans to set-indicator …
- Algebraic Hashing: Composable Hash Functions Through XOR · November 2022A C++ library for composable hash functions using algebraic structure over XOR, with template metaprogramming.
- Rank-Ordered Encrypted Search · June 2021Rank-ordered search over encrypted documents using oblivious entropy maps, enabling relevance scoring without revealing document contents.
- Random Oracles in Python · June 2016Three Python approximations of a random oracle, each showing a different tradeoff between true randomness, determinism, and composability.
Foundations
The framework grew from a set of authentic 2023-2024 notes, the Bernoulli model, noisy gates, Boolean algebra over trapdoors, and entropy maps, collected under the series and its recommended reading, which places the work against the searchable-encryption canon, the oblivious-RAM literature, and the approximate-set data structures it generalizes.
Alexander Towell, metafunctor.com.