Privacy through Indistinguishable Query Results

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 28 papers15 conceptsfrozen 2026-10-04

When a system refuses to answer a query or returns an empty result, it often reveals more than intended. In secure data environments, the central challenge is not just hiding sensitive values, but ensuring that the absence of information does not signal its existence. The research direction across these papers focuses on indistinguishability: a state where a user cannot differentiate between a world where a secret is intentionally hidden and a world where that secret simply does not exist.

The Problem of Partial Leakage

Traditional access control often fails because it leaks "meta-information." If a user queries a database for a specific record and the system returns a "permission denied" error, the user immediately learns that the record exists.

To solve this, Brent Waters introduced Hidden Vector Encryption (HVE) in Conjunctive, Subset, and Range Queries on Encrypted Data. The intuition here is an "all-or-nothing" property. In a multi-part (conjunctive) query, the evaluator should only learn the final boolean result. If the query fails, the system must not reveal which specific attribute caused the mismatch. By making the evaluation atomic, the system prevents an adversary from piecing together sensitive attributes through partial matches.

Plausible Deniability through Alternative Datasets

In complex systems like Ontology-Based Data Integration (OBDI), privacy is harder to maintain because different data points are logically linked. A user might infer a hidden fact by combining a public query result with their knowledge of how the data is structured.

Michael Benedikt, Bernardo Cuenca Grau, and Egor V. Kostylev established a formal foundation for this in Source Information Disclosure in Ontology-Based Data Integration. They argue that privacy is only achieved if, for every sensitive fact in the source data, there exists at least one "indistinguishable alternative dataset" where that fact is false but all query outputs remain the same.

This concept is operationalized through skeptical entailment. As explored by Gianluca Cima and colleagues in Enhancing Controlled Query Evaluation through Epistemic Policies, the system only returns results that are true across all possible versions of the database that satisfy the privacy policy. This ensures the user cannot tell if a fact is missing because it was censored or because it was never there to begin with.

Statistical Indistinguishability

While logical indistinguishability works for discrete facts, statistical databases require a different approach. The goal remains the same: the output should not reveal whether a specific individual's data was used.

In their foundational work, Moni Naor and Cynthia Dwork argue in On the Difficulties of Disclosure Prevention in Statistical Databases that absolute privacy is impossible. Instead, they propose Differential Privacy, which guarantees that the inclusion or exclusion of a single individual does not significantly change the distribution of the output.

This idea is extended to more complex, multi-user scenarios by Ni Ding and Zijian Zhang in Multi-user Pufferfish Privacy. By using the Wasserstein distance to calibrate noise, they ensure that a user’s privacy is protected regardless of how likely they were to participate in the dataset.

Protecting the "Secret Sauce"

Indistinguishability isn't just for raw data; it also applies to the processes that handle it. In scientific workflows, the "provenance" (the history of how data was processed) can leak proprietary logic.

Debmalya Panigrahi, Susan B. Davidson, and their co-authors address this in Preserving Module Privacy in Workflow Provenance. They propose a privacy metric that ensures multiple potential outputs remain plausible for any given input. By hiding just enough of the workflow's intermediate steps, the system ensures the underlying "module functionality" remains indistinguishable from other possible functions, protecting the researcher's proprietary methods while maintaining data utility.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 12 papers
  2. Version 1 · 2026-10-04 · 8 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_probabilistic_output_indistinguishabilit_a12e1fdb,
  title = {probabilistic output indistinguishability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-output-indistinguishability/rdr_a12e1fdb02bd40689229ae205f893c20},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_privacy_through_indistinguishable_query__a12e1fdb_v1,
  title = {Privacy through Indistinguishable Query Results},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/privacy-through-indistinguishable-query-results/rdr_a12e1fdb02bd40689229ae205f893c20/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}