Noisy Turing Machines: Noisy Logic Gates
Analyzing how Bernoulli Boolean types propagate through logic circuits, with correctness probabilities for noisy AND gates and interval arithmetic for composed circuits.
2
of 7
← All Series
Trapdoor Computing
A paradigm for computing with values whose meaning is hidden behind a one-way trapdoor. Cipher maps, approximate homomorphisms, and a framework for oblivious function evaluation.
Trapdoor Computing
A paradigm for computing with values whose meaning is hidden behind a one-way trapdoor.
The Idea
A cipher map is a total function on bit strings. Every input produces output. The concepts of “domain,” “correct,” and “incorrect” only exist on the trusted machine that holds the decoder. The untrusted machine sees only opaque bits flowing through opaque lookup tables; it cannot distinguish signal from noise.
Foundations
The foundations/ directory contains the authentic source documents (2023-2024) that define the framework:
- bernoulli-model.md: The Bernoulli Model. Latent/observed duality, confusion matrices, HashSet construction achieving
-log_2(epsilon)bits per element. - noisy-gates.md: Noisy Turing Machines. Composing Bernoulli logic gates, interval arithmetic for error propagation through circuits.
- trapdoor-boolean-algebra.md: Boolean Algebra Over Trapdoors. Approximate homomorphism from powerset to bit strings via cryptographic hash, marginal uniformity.
- entropy-maps.md: Entropy Maps. Prefix-free hash codes for function approximation, mu = H(Y) space bound, two-level hash construction.
Four Properties of a Cipher Map
A cipher map f-hat implementing a latent function f satisfies:
- Totality: f-hat is defined on all inputs (bits in, bits out). Out-of-domain inputs produce random output. With probability epsilon, random output happens to be a valid codeword.
- Representation Uniformity: Each domain value has multiple encodings. The distribution over encodings is delta-close to uniform, preventing frequency analysis.
- Correctness: For in-domain inputs, decode(f-hat(encode(x))) = f(x) with probability at least 1 - eta.
- Composability: Composing cipher maps compounds error predictably: eta_total = 1 - (1 - eta_f)(1 - eta_g).
Further Reading
See Recommended Reading, for the searchable-encryption canon (Song-Wagner-Perrig, Curtmola et al.), oblivious-RAM literature (Goldreich-Ostrovsky, Path ORAM), and the approximate-set data structures (Bloom, cuckoo, MPHF) that this framework generalizes.
Author
Alexander Towell, metafunctor.com
Posts in this Series
Showing 18 of 18 posts
2
of 7
Entropy Maps
Entropy maps use prefix-free hash codes to approximate functions without storing the domain, achieving information-theoretic space bounds with controllable error.
3
of 7
Perfect Hashing: Space Bounds, Entropy, and Cryptographic Security
Space bounds, entropy requirements, and cryptographic security properties of perfect hash functions.
4
of 7
A Boolean Algebra Over Trapdoors
A 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 computations with one-way properties.
5
of 7
Algebraic Hashing: Composable Hash Functions Through XOR
A C++ library for composable hash functions using algebraic structure over XOR, with template metaprogramming.
6
of 7
Rank-Ordered Encrypted Search
Rank-ordered search over encrypted documents using oblivious entropy maps, enabling relevance scoring without revealing document contents.
7
of 7
Random Oracles in Python
Three Python approximations of a random oracle, each showing a different tradeoff between true randomness, determinism, and composability.