Strategic Information Hiding and the Complexity of Privacy

This direction is merged into another direction: centrality evasion complexity. Its last version stays readable and citable here.

Version 1 of 126 papers33 conceptsfrozen 2026-10-04

In an era of ubiquitous data, the tension between transparency and secrecy has moved beyond simple encryption. Whether it is a scientist sharing a workflow, a social media user protecting their relationships, or a hospital releasing genomic data, the goal is the same: provide enough information to be useful while hiding the "secret sauce" or sensitive identities.

This research direction explores Strategic Information Hiding—the formal study of how to optimally modify data to evade detection or inference. The recurring discovery across this field is a sobering one: finding the mathematically perfect way to hide information is almost always computationally intractable. However, researchers have found that while "perfect" privacy is hard to calculate, "good enough" privacy is often achievable through clever heuristics.

The Seeker-Evader Game

At the heart of this field is a shift in how we view privacy. Rather than seeing data subjects as passive entities, researchers like Tomasz P. Michalak, Michael J. Wooldridge, and Talal Rahwan frame the problem as a Seeker-Evader game. In Strategic Social Network Analysis, they argue that actors (the Evaders) strategically manipulate their connections to avoid being flagged by analysts (the Seekers).

This framing applies to various domains:

The Computational Wall

If we want to hide a connection in a network, why not just find the "best" set of links to delete? The core challenge identified by researchers is that optimal hiding is NP-hard.

In How to Hide One’s Relationships from Link Prediction Algorithms, Marcin Waniek and colleagues prove that for most similarity-based metrics, finding the minimum number of changes to hide a link is NP-complete. The complexity arises because data points are correlated. In a network, removing one edge changes the "closeness" or "betweenness" of many other nodes. In a dataset, generalizing one attribute to protect a record might inadvertently reveal something about another record due to the "minimality" of the algorithm itself—a phenomenon known as the Minimality Attack (Minimality Attack in Privacy Preserving Data Publishing).

This intractability extends to:

Why Heuristics Work

If the problem is NP-hard, how can we ever protect privacy? The intuition provided by this research is that local changes often yield global results.

While finding the absolute best set of modifications is hard, simple "rewiring" strategies—like unfriending a few mutual contacts—can effectively blind link prediction algorithms. Waniek and Michalak demonstrate that polynomial-time heuristics can approximate the optimal solution well enough to protect users in large-scale networks.

Similarly, in medical research, Raymond Heatherly and Bradley Malin show that by anonymizing small cohorts against a massive background population, they can preserve 100% of scientific utility while maintaining privacy (Enabling Genomic-Phenomic Association Discovery without Sacrificing Anonymity). They use heuristic-driven generalization to bypass the NP-hard complexity of finding the perfect attribute mapping.

New Frontiers: Information Theory and Quantum

Recent work has pushed this strategic hiding into more abstract mathematical and physical realms. Shuaiqi Wang and Zhiwei Steven Wu have developed frameworks for Blackwell-optimal disclosure, which seeks the most useful information release that still strictly limits what an observer can infer about a secret (Inferentially-Private Private Information).

On the computational side, researchers are even looking toward quantum computing to solve these hiding problems. Yan Li and Sumit Sarkar proposed using the Quantum Approximate Optimization Algorithm (QAOA) to hide sensitive frequent itemsets in databases, mapping the NP-hard combinatorial problem to a quantum Ising model (A Quantum Algorithm Based Heuristic to Hide Sensitive Itemsets).

Summary

Strategic Information Hiding teaches us that privacy is not a static shield but an active, algorithmic struggle. While the complexity of data relationships makes "perfect" hiding a computationally impossible task, the use of strategic heuristics allows us to navigate the trade-off between sharing useful insights and protecting the underlying secrets.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_strategic_information_hiding_and_the_com_49a8e6ff,
  title = {Strategic Information Hiding and the Complexity of Privacy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/strategic-information-hiding-and-the-complexity-of-privacy/rdr_49a8e6ffac584c7cbbbc5ca9b631bcdd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_strategic_information_hiding_and_the_com_49a8e6ff_v1,
  title = {Strategic Information Hiding and the Complexity of Privacy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/strategic-information-hiding-and-the-complexity-of-privacy/rdr_49a8e6ffac584c7cbbbc5ca9b631bcdd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}