IEEE Paper: Estimating How Confidential Encrypted Searches Are Using Moving Average Bootstrap Method
Published IEEE paper on using bootstrap methods to estimate encrypted search confidentiality against frequency attacks.
1
of 14
← All Series
Oblivious & Approximate Computing
A blog series exploring encrypted search, Bernoulli models, cipher types, and probabilistic data structures
Oblivious & Approximate Computing
This series explores the mathematical foundations of computing on encrypted and approximate data—where we deliberately trade exactness for privacy, space efficiency, or computational tractability.
Core Themes
1. The Latent/Observed Duality
The fundamental insight: distinguish between latent (true) values and observed (approximate) values. This duality connects:
- Probabilistic data structures (Bloom filters, sketches)
- Privacy mechanisms (information-theoretic privacy)
- Encrypted search systems (oblivious query processing)
2. Bernoulli Types
A type-theoretic framework for approximate computing:
- Formal semantics for approximate operations
- Composition rules with error propagation
- Space-optimal constructions for any probability distribution
3. Cipher Maps & Algebraic Cipher Types
Category-theoretic foundations for encrypted computation:
- Functorial lifting of algebraic structures
- Homomorphic operations preserving structure
- Privacy through rank-deficient observation functions
4. Information-Theoretic Privacy
Moving beyond computational hardness assumptions:
- Privacy from controlled indistinguishability
- Entropy-optimal index construction
- Asymptotic privacy guarantees
Key Papers
- Encrypted Search with Oblivious Bernoulli Types - Using approximate data structures for privacy
- Maximizing Confidentiality Through Entropy - Optimal parameterization of secure indexes
- Cipher Maps - Categorical foundations for encrypted computation
- Perfect Hashing with Cryptographic Security - Space-optimal, maximum-entropy hash functions
Why This Matters
In an era where:
- Privacy is non-negotiable, but exact computation leaks information
- Scale demands approximation—you can’t store everything exactly
- Streaming data requires constant-space algorithms
- Encrypted search needs oblivious data structures
…these foundations provide principled ways to build systems that trade exactness for other desirable properties while maintaining formal guarantees.
About
This work builds on research spanning from my Master’s thesis (2015) on encrypted search through recent work on algebraic cipher types and entropy maps. The combination of Bernoulli types with categorical abstractions finally provides a unified mathematical foundation for practical privacy-preserving computation at scale.
Posts in this Series
Showing 25 of 25 posts
2
of 14
Entropy Maps: When Hashing Meets Information Theory
A conceptual introduction to entropy maps—implementing functions with hash functions and prefix-free codes.
3
of 14
Bernoulli Types: A New Foundation for Approximate and Oblivious Computing
I’ve been working on a series of papers that develop a unified theoretical framework for approximate and oblivious computing, centered around what I call Bernoulli types. These papers explore …
4
of 14
Cipher Maps: When Category Theory Meets Oblivious Computing
What if we could compute on encrypted data while preserving algebraic structure? Not through expensive homomorphic encryption, but through a principled mathematical framework that unifies oblivious …
5
of 14
Rethinking Encrypted Search: From Access Pattern Leakage to Information-Theoretic Privacy
Encrypted search has a fundamental problem: you can’t hide what you’re looking for. Even with the best encryption, search patterns leak information. My recent work develops a new approach …
6
of 14
Algebraic Cipher Types: Computing on Encrypted Data While Preserving Structure
A functorial framework that lifts algebraic structures into the encrypted domain, enabling secure computation that preserves mathematical properties.
7
of 14
Entropy Maps
The PDF version of this post is available on GitHub.
The basic theory behind an entropy map is to map values in the domain to values in the codomain by hashing to a prefix-free code in the codomain. …
8
of 14
Known Plaintext Attacks on Time Series Encryption
Analysis of known plaintext attack vulnerabilities in time series encryption schemes.
9
of 14
Perfect Hashing: Space Bounds, Entropy, and Cryptographic Security
What if a perfect hash function could simultaneously be: (1) cryptographically secure, (2) space-optimal, and (3) maximum-entropy encoded? This paper proves such a construction exists—and analyzes …
10
of 14
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.
11
of 14
The Bernoulli Model: A Probabilistic Framework for Data Structures and Types
This blog post introduces the Bernoulli Model, a framework for understanding probabilistic data structures and incorporating uncertainty into data types, particularly Boolean values. It highlights the model's utility in optimizing space and accuracy in data representation.
12
of 14
Algebraic Hashing: Composable Hash Functions Through XOR
Most hash libraries treat hash functions as black boxes. Algebraic Hashing exposes their mathematical structure, letting you compose hash functions like algebraic expressions—with zero runtime …
13
of 14
Rank-Ordered Encrypted Search
Exploring rank-ordered search over encrypted documents using oblivious entropy maps, enabling relevance scoring without revealing document contents.
14
of 14
Bloom Filters and the Art of Probabilistic Certainty
One of the most elegant ideas I encountered during my CS masters work is the Bloom filter—a data structure that gives you probabilistic membership testing with extraordinary space efficiency.