Boolean Encrypted Search with Approximate Sets:
Error Propagation, Query Obfuscation, and Threshold-Based Retrieval

Classical precision is defined as $\mathrm{Prec}=\left|ℝ\cap {ℝ}^{\ast }\right|/\left|{ℝ}^{\ast }\right|$. Because hidden queries do not incur false negatives, the numerator equals $\left|ℝ\right|$. Taking expectations gives the deterministic upper bound

Recall remains identically $1$; the encrypted setting preserves completeness while trading a tunable amount of precision for storage and compute efficiency. The expected F₁ score simplifies accordingly:

Suppose $N={10}^6$ documents contain $\left|ℝ\right|=3\times {10}^3$ relevant results. With query length $r=4$ and per-trapdoor false-positive probability $\epsilon =2^{-10}$, the compound probability is ${\epsilon }_q=2^{-40}\approx 9.1\times {10}^{-13}$. The expected number of false positives is therefore $𝔼[F]\approx {10}^{-6}$, so precision remains effectively $1$. Even when $\epsilon$ is relaxed to $2^{-4}$ the expected number of spurious matches is $\approx 0.96$, demonstrating how aggressively the system can tune $\epsilon$ before precision begins to degrade.

These expressions make explicit how design choices for the secure index (hash family, filter width, load factor) influence observable retrieval quality. In Section 3.2 we connect $\epsilon$ to concrete data-structure parameters, enabling end-to-end sizing of encrypted search deployments.

Table 1 summarises the false positive and false negative rates for the five basic Boolean query patterns. When $\delta =0$, the FNR column simplifies: conjunctions and disjunctions exhibit zero false negatives, while negations swap all error probability to the FNR term.

Logically equivalent Boolean expressions can exhibit dramatically different error rates. For instance, a conjunctive query $a_1\wedge \mathrm{\cdots }\wedge a_r$ has $\text{FPR}={\epsilon }^r$, which decreases exponentially with $r$. Disjunctive queries, conversely, have $\text{FPR}\approx r\epsilon$ for small $\epsilon$, growing linearly. Users or query optimisers can exploit this asymmetry: rewriting disjunctions as unions of conjunctive subqueries may reduce aggregate false positive rates when combined with client-side filtering.

Theorems 4.3 and 4.6 show that negation exchanges FPR and FNR. Systems built on approximate sets with $\delta =0$ sacrifice perfect recall when queries involve negation. If maintaining high recall is critical, queries should avoid or minimise negation depth. Alternatively, systems could implement exact membership structures for a subset of high-value terms, enabling precise negation without FNR degradation.

Given $\epsilon$, $\delta$, and a query $Q$, Algorithm 6 computes $\text{FPR}(Q)$ and $\text{FNR}(Q)$ before execution. These rates directly determine expected precision and recall. Extending the analysis from Section 3.1, suppose the exact result set has cardinality $\left|ℝ\right|$ and the collection contains $N$ documents. The expected number of false positives is

and the expected number of false negatives is

Expected precision and recall become

When $\delta =0$ and $Q$ is a pure conjunction or disjunction (no negation), Equation 4.32 yields $𝔼[\text{Rec}]=1$, recovering the perfect-recall guarantee from Section 3.

The storage cost of an approximate set is proportional to ${\log }_2(1/\epsilon )$ (see Section 3.2). Designers can select $\epsilon$ to balance space and error rates. Table 1 shows that conjunctions benefit from aggressive compression (small $\epsilon$), since FPR scales as ${\epsilon }^r$. Disjunctions and negations, however, degrade more gracefully, suggesting that mixed-mode indexes—high precision for conjunctive subqueries, moderate precision for disjunctive expansions—may be cost-effective.

In the baseline unigram model, every query consists of individual term lookups: $\{\mathrm{h}(a++k),\mathrm{h}(b++k),\mathrm{h}(c++k)\}$. An adversary observing the server learns:

1. 1.

   The exact query cardinality (three terms)

2. 2.

   Co-occurrence patterns of these three terms across the document collection

3. 3.

   The distribution of queries, which mirrors the plaintext query distribution (just with substituted trapdoors)

4. 4.

   Statistical correlations enabling frequency analysis or query reconstruction attacks

A $k$-graph with $k\ge 3$ replaces this with a single compound trapdoor: $\mathrm{h}({\{a,b,c\}}_{\text{AND}}++k)$ for conjunction or $\mathrm{h}({\{a,b,c\}}_{\text{OR}}++k)$ for disjunction. The adversary observes only that some compound trapdoor was queried, without learning:

• •

  How many distinct terms are encoded (could be 1 to $k$)

• •

  Which specific terms are involved

• •

  Whether this represents a genuine $k$-term query or a padded lower-cardinality query

• •

  The true distribution of plaintext queries

This fundamentally breaks the isomorphism between encrypted and plaintext query distributions. Where the baseline model applies a simple substitution cipher to queries (preserving all distributional properties), $k$-graphs introduce entanglement: terms are cryptographically combined in ways that obscure their individual identities and relationships.

Suppose a document contains $n$ unique search keys. A $k$-graph stores trapdoors for all subsets of size at most $k$, tagged with Boolean operations (AND, OR). For each subset of size $j\in [1,k]$, we store both the AND-tagged and OR-tagged trapdoor (and potentially NOT-tagged, though space constraints often limit this). Thus the number of trapdoors is:

Using Equation 3.7, the storage requirement is

For specific values of $k$ (with both AND and OR tags):

• •

  $k=1$ (baseline): $𝒪(n)$ trapdoors, $2n{\log }_2(1/\epsilon )$ bits

• •

  $k=2$ (digraphs): $𝒪(n^2)$ trapdoors, $n(n+1){\log }_2(1/\epsilon )$ bits

• •

  $k=3$ (trigraphs): $𝒪(n^3)$ trapdoors, $2\left(n+\frac{n(n+1)}{2}+\frac{n(n+1)(n+2)}{6}\right){\log }_2(1/\epsilon )$ bits

• •

  $k=n$ (power set): $𝒪(2^n)$ trapdoors, $2(2^n-1){\log }_2(1/\epsilon )$ bits

Example 6 [Concrete storage costs] Consider a typical document with $n=100$ unique search keys (e.g., a 500-word document with Zipf-distributed vocabulary). Storage requirements for various configurations (including both AND and OR tags):

$k$	$\epsilon$	Trapdoors	Storage
1	$2^{-10}$	200	2.0 KB
1	$2^{-4}$	200	0.8 KB
2	$2^{-10}$	10,100	101 KB
2	$2^{-4}$	10,100	40.4 KB
3	$2^{-10}$	343,400	3.4 MB
3	$2^{-4}$	343,400	1.37 MB

The digraph case $(k=2)$ increases storage by $\sim$50$\times$ over baseline, while the trigraph case $(k=3)$ inflates it by $\sim$1700$\times$. This exponential growth makes elevated $\epsilon$ essential: using $\epsilon =2^{-4}$ instead of $\epsilon =2^{-10}$ reduces storage by 2.5$\times$, making the trigraph index feasible at 1.37 MB per document instead of 3.4 MB.

For a smaller document with $n=20$ unique keys (e.g., an email or short article), storage becomes more manageable:

$k$	$\epsilon$	Trapdoors	Storage
2	$2^{-4}$	420	1.68 KB
3	$2^{-4}$	3,080	12.3 KB
4	$2^{-4}$	17,710	70.8 KB

Here even $k=4$ remains practical, enabling strong obfuscation for up to 4-term queries with modest overhead.

This substantial storage overhead is precisely why the system’s tolerance for elevated false positive rates becomes advantageous. Recall from Section 4 that conjunctive queries with $r$ terms achieve $\text{FPR}={\epsilon }^r$, which decreases exponentially. If atomic trapdoors use $\epsilon =2^{-4}$, a three-term query has effective FPR $\approx 2^{-12}\approx 2.4\times {10}^{-4}$, yielding near-perfect precision even with aggressive compression. The analysis in Section 3.1 demonstrated that precision remains acceptable even at $\epsilon =2^{-4}$ for realistic workloads. By accepting modestly elevated $\epsilon$, we obtain order-of-magnitude storage reductions that make $k$-graph indexes practical:

A fundamental property of $k$-graphs is that they provide inherent cardinality obfuscation: any query with at most $k$ distinct terms collapses to a single trapdoor lookup, making it impossible for the server to determine the true number of terms. A 1-term query $\mathrm{h}({\{a\}}_{\text{AND}}++k)$ and a 3-term query $\mathrm{h}({\{a,b,c\}}_{\text{AND}}++k)$ both appear as single compound trapdoor lookups to the server. The adversary observes only that some $j$-graph trapdoor (for $j\in [1,k]$) was queried, but learns nothing about which $j$ or which specific terms are encoded.

This stands in stark contrast to the baseline unigram model, where query cardinality is immediately observable: a 3-term query requires three separate trapdoor lookups, directly revealing the query size.

While $k$-graphs already mask cardinality, the client can further obscure the query distribution by exploiting multiple encodings of the same logical query. For a single search term $a$, the following trapdoors are all semantically equivalent (each matches documents containing $a$):

• •

  $\mathrm{h}({\{a\}}_{\text{AND}}++k)$ (unigram encoding)

• •

  $\mathrm{h}({\{a,a\}}_{\text{AND}}++k)$ (repeated bigram encoding)

• •

  $\mathrm{h}({\{a,a,a\}}_{\text{AND}}++k)$ (repeated trigram encoding)

• •

  etc., up to $\mathrm{h}({\{a,a,\mathrm{\dots },a\}}_{\text{AND}}++k)$ with $k$ repetitions

Because conjunction is idempotent ($a\wedge a\equiv a$), all encodings yield identical results. However, each produces a cryptographically distinct trapdoor due to the hash function. By randomly selecting among these $k$ encodings each time term $a$ is queried, the client distorts the observable query distribution:

• •

  The baseline model preserves the plaintext query distribution (just with substituted trapdoors)

• •

  With term repetition, the same logical query appears as $k$ different trapdoors over time

• •

  The server observes a flattened, artificially uniform distribution that bears no statistical relationship to the underlying plaintext query patterns

This breaks frequency analysis attacks: even if term $a$ dominates the plaintext query distribution, its $k$ encoded representations appear with $1/k$ the frequency each, obscuring which trapdoors correspond to popular versus rare queries.

The error rates remain unchanged: from Section 4, $\text{FPR}(a\wedge a\wedge \mathrm{\cdots }\wedge a)=\text{FPR}(a)$ and $\text{FNR}(a\wedge a\wedge \mathrm{\cdots }\wedge a)=\text{FNR}(a)$ due to idempotence. Distribution obfuscation via term repetition adds no accuracy degradation.

For disjunctive queries, the client can inject fake trapdoors—randomly sampled hash values that correspond to no actual search terms—to further obfuscate query structure. Consider a 2-term disjunctive query $\{a,b\}$ submitted to a $k=4$ index. The client can augment it with noise:

where $r_1$ and $r_2$ are random hash values. Because disjunction semantics mean “match if any term is present,” the fake trapdoors are unlikely to affect query results: they test positive only with probability $\epsilon$ (the base false positive rate). For typical $\epsilon =2^{-4}$ to $2^{-10}$, the probability that a fake trapdoor causes a spurious match is negligible.

This technique provides controlled noise injection: the server observes a 4-term OR query but cannot determine which terms are genuine versus fake. Unlike conjunctive queries (where every term must match, so fake terms would break the query), disjunctions tolerate noise gracefully. The expected number of false positives introduced by $m$ fake trapdoors is approximately $(N-|ℝ|)\cdot m\epsilon$ additional spurious documents, which remains small for reasonable $m$ and $\epsilon$.

Fake trapdoor injection is particularly effective when combined with term repetition: the client can pad a disjunctive query with both repeated genuine terms (for distribution obfuscation) and random fake terms (for cardinality inflation beyond $k$ genuine terms), creating maximum uncertainty about query structure.

While $k$-graphs do reduce query round-trips (a query with $p$ terms requires $\lceil p/k\rceil$ trapdoor lookups instead of $p$), this performance benefit is secondary. The dominant cost in encrypted search is typically index transfer and client-side decryption, not the number of membership tests. The primary motivation is security:

• •

  Inherent cardinality concealment: Any query with $\le k$ distinct terms becomes a single trapdoor lookup, making it impossible to distinguish 1-term from $k$-term queries.

• •

  Term correlation hiding: Co-occurrence patterns of search keys become opaque to the server, as multi-term queries are cryptographically entangled.

• •

  Distribution obfuscation: Term repetition provides $k$ distinct encodings per query, flattening the observable distribution and breaking the isomorphism with plaintext query patterns.

• •

  Frequency analysis resistance: Popular queries appear as multiple distinct trapdoors with $1/k$ the frequency each, obscuring which trapdoors correspond to common versus rare queries.

• •

  Temporal unlinkability: The same logical query appears as different trapdoors across time when using randomized encodings, preventing the server from linking repeated queries.

• •

  Noise injection compatibility: OR queries can incorporate fake trapdoors with minimal accuracy impact, further distorting observable query patterns.

Together, these mechanisms trade storage complexity (exponential in $k$) and time complexity (construction cost grows with $k$) for substantial reductions in information leakage. The system’s tolerance for elevated $\epsilon$ makes this tradeoff practical.

System designers should select $k$ based on adversarial threat models, query patterns, and storage budgets:

• •

  $k=1$ (baseline): Minimal storage, maximum leakage. Query distribution mirrors plaintext distribution (modulo substitution). Suitable when the server is semi-trusted or queries are low-sensitivity.

• •

  $k=2$ (digraphs): Moderate storage ($\sim 50\times$ overhead), conceals pairwise term correlations. Enables 2-term queries as single trapdoors and provides 2 distinct encodings per term for distribution flattening.

• •

  $k=3$ (trigraphs): Substantial storage ($\sim 1700\times$ overhead), strong obfuscation. Supports up to 3-term queries as single lookups, provides 3 encodings per term, and enables meaningful fake trapdoor injection for OR queries. Practical when $\epsilon =2^{-4}$ is acceptable.

• •

  $k\ge 4$: Exponential storage growth, near-maximal obfuscation. Justifiable for high-value/high-sensitivity workloads with small document vocabularies (e.g., $n\le 20$ unique terms).

• •

  $k=n$ (full power set): Complete obfuscation—every possible query becomes a single trapdoor lookup, and every term has $n$ distinct encodings. Practical only for very small vocabularies or documents.

The key insight is that $k$-graphs and elevated $\epsilon$ work synergistically: the system’s ability to maintain acceptable precision at $\epsilon =2^{-4}$ (due to exponential FPR decay in conjunctive queries) makes the substantial storage overhead tolerable. Combined with term repetition and fake trapdoor injection, $k$-graphs enable meaningful query privacy enhancements by breaking the distributional link between encrypted and plaintext query patterns.