Skip to main content

Trapdoor Computing: Recommended Reading

4 min read Updated:

Recommended Reading

This list extends the Trapdoor Computing series with the prior art that the cipher-map framework reframes. Entries marked ✦ are the works I would hand someone starting out; the rest is depth.

The sections mirror the structure of the series: classical searchable encryption first, then oblivious-access primitives, then the approximate-set data structures the Bernoulli Model generalizes, then the information-theoretic foundations.

Searchable Encryption

The classical literature on search over encrypted data. The framework under which “cipher map” can be read as a generalization.

  • Practical Techniques for Searches on Encrypted Data by Song, Wagner, Perrig (2000) [paper] ✦. The paper that started the field. IEEE S&P.
  • Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions by Curtmola, Garay, Kamara, Ostrovsky (2006) [paper] ✦. Established the modern security definitions (IND-CKA1, IND-CKA2) for SSE. IACR.
  • Secure Indexes by Goh (2003) [paper]. Z-IDX, the Bloom-filter-backed secure index. One of the direct ancestors of the cipher-map construction. IACR.
  • Public Key Encryption with Keyword Search by Boneh, Di Crescenzo, Ostrovsky, Persiano (2004) [paper]. PEKS: the public-key counterpart to SSE. IACR.
  • Privacy Preserving Keyword Searches on Remote Encrypted Data by Chang, Mitzenmacher (2005) [paper]. Extends Goh with keyword indexes.

Oblivious Computation

Access-pattern hiding and oblivious execution. The lineage that motivates the cipher-map focus on representation uniformity and indistinguishability of access.

  • Software Protection and Simulation on Oblivious RAMs by Goldreich, Ostrovsky (1996) [paper] ✦. The foundational ORAM paper. JACM 43(3).
  • Path ORAM: An Extremely Simple Oblivious RAM Protocol by Stefanov, van Dijk, Shi, Fletcher, Ren, Yu, Devadas (2013) [paper]. Modern, practical ORAM. CCS.
  • Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits by Garg, Gentry, Halevi, Raykova, Sahai, Waters (2013) [paper]. The iO construction. Adjacent but conceptually important for anyone thinking about functional concealment.

Approximate Set Data Structures

The engineering half of the series. These are the constructions the Bernoulli Model generalizes and the cipher-map implements.

  • Space/Time Trade-offs in Hash Coding with Allowable Errors by Bloom (1970) [paper] ✦. The Bloom filter. One of the most-cited data-structures papers in CS. CACM 13(7).
  • Cuckoo Filter: Practically Better Than Bloom by Fan, Andersen, Kaminsky, Mitzenmacher (2014) [paper]. Hash-cuckoo-based approximate set with deletions and better space efficiency. CoNEXT.
  • Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters by Graf, Lemire (2020) [paper]. Tight approximate-set construction approaching the information-theoretic lower bound.
  • Hash, Displace, and Compress by Belazzougui, Botelho, Dietzfelbinger, Pagh (2009) [paper] ✦. CHD: one of the cleanest minimal perfect hash function constructions.
  • RecSplit: Minimal Perfect Hashing via Recursive Splitting by Esposito, Graf, Vigna (2020) [paper]. Practical near-optimal MPHF.
  • Network Applications of Bloom Filters: A Survey by Broder, Mitzenmacher (2004) [paper]. The classic survey.

Information-Theoretic Foundations

Where the model grounds its claims about confidentiality, leakage, and the optimality of specific constructions.

  • Communication Theory of Secrecy Systems by Shannon (1949) [paper] ✦. The origin of information-theoretic cryptography. Still the cleanest statement of what unconditional security means.
  • Elements of Information Theory by Cover, Thomas (2006, 2nd ed.) [book] ✦. Standard reference for entropy, mutual information, channel coding. Used throughout the trapdoor entropy analyses.
  • Foundations of Cryptography (Vol I and II) by Goldreich (2001, 2004) [book]. Definitional rigor for computational security. The lens through which “indistinguishability” is formalized.
  • Serious Cryptography by Aumasson (2017) [book]. Modern applied-crypto reference; good complement to Goldreich for implementers.

How this list is opinionated

The thread: computation over values whose meaning is hidden behind a one-way trapdoor, implemented via approximate-set data structures that enforce representation uniformity and bounded leakage. Works that illuminate this thread are in.

Excluded, not because they are bad but because they belong to other books: fully homomorphic encryption (Gentry 2009 and successors, a different computational model), secure multiparty computation (Yao, GMW, BGW), modern lattice-based post-quantum schemes. The cipher-map framework interacts with these but does not depend on them.

If you read three things before everything else, read Shannon 1949, Song-Wagner-Perrig 2000, and the Bloom 1970 paper. Those three together set up the questions the series is trying to answer.