Database Reconstruction

Imagine a hospital database that will never show you individual records, but will happily answer statistical queries: How many patients over 60 have hypertension? or What is the average cholesterol of diabetic women? Seems safe — no individual is ever named.

In 2003, Irit Dinur and Kobbi Nissim proved that this intuition is wrong. Given enough accurate answers to linear counting queries, an attacker can reconstruct the exact private values of every individual in the database. The more accurate the answers, the easier the reconstruction.

This is not an exotic hack — it is a mathematical law. Accuracy and privacy are in fundamental tension: you cannot have both at the same time, at least not without noise. The theorem set the theoretical foundation for differential privacy, the modern framework that turns this impossibility into a precise budget for how much noise to add.

Below is a secret binary vector of 6 values — each is 0 or 1, representing a private database row. You cannot see it directly, but you can ask linear counting queries: each query reveals the sum of a subset of the entries.

<!-- {{c_layout_comment}} -->
<p class="hint">{{hint_para}}</p>
<div class="panel">
  <div class="secret-row">
    <span class="label">{{label_secret}}</span>
    <div id="secret-display" class="bit-row hidden-bits"></div>
    <button id="reveal-btn" type="button" class="ghost small">{{btn_reveal}}</button>
  </div>
  <div class="candidates-row">
    <span class="label">{{label_candidates}}</span>
    <span id="cand-count" class="count-badge">64</span>
  </div>
</div>
<div class="query-panel">
  <p class="query-label">{{label_pick_query}}</p>
  <div id="query-checkboxes" class="query-bits"></div>
  <div class="query-row">
    <button id="ask-btn" type="button">{{btn_ask}}</button>
    <span id="query-result" class="query-result"></span>
  </div>
</div>
<div id="history" class="history"></div>
<div class="btns">
  <button id="auto-btn" type="button">{{btn_auto}}</button>
  <button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="status" class="status"></div>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: .93rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.4; }
.panel { background: #f0f4f8; border-radius: 10px; padding: .7rem 1rem; margin-bottom: .7rem; }
.secret-row, .candidates-row { display: flex; align-items: center; gap: .6rem; margin: .25rem 0; }
.label { font-size: .8rem; font-weight: 600; color: #555; min-width: 100px; }
.bit-row { display: flex; gap: 4px; }
.bit { width: 32px; height: 32px; border-radius: 6px; display: flex; align-items: center;
       justify-content: center; font: 700 15px ui-monospace, monospace; }
.bit-0 { background: #d1e8ff; color: #1a5fa0; border: 1px solid #99c4ef; }
.bit-1 { background: #ffd6d6; color: #9b1c1c; border: 1px solid #f5a0a0; }
.bit-hidden { background: #c9ccd1; color: transparent; border: 1px solid #adb1b8; }
.count-badge { background: #1d3557; color: #fff; border-radius: 20px; padding: .1rem .6rem;
               font-weight: 700; font-size: .9rem; transition: background .3s; }
.count-badge.solved { background: #0a7d33; }
.small { font-size: .78rem; padding: .2rem .55rem; }
.query-panel { border: 1px solid #cdd9e3; border-radius: 10px; padding: .7rem 1rem; margin-bottom: .6rem; }
.query-label { font-size: .82rem; font-weight: 600; color: #444; margin: 0 0 .4rem; }
.query-bits { display: flex; gap: 6px; flex-wrap: wrap; margin-bottom: .5rem; }
.qb { width: 38px; height: 38px; border-radius: 8px; border: 2px solid #cdd9e3;
      background: #f5f7fa; cursor: pointer; display: flex; align-items: center;
      justify-content: center; font: 700 13px ui-monospace, monospace; color: #555;
      transition: all .1s; user-select: none; }
.qb.selected { background: #1d3557; color: #fff; border-color: #1d3557; }
.query-row { display: flex; align-items: center; gap: .6rem; }
.query-result { font-weight: 700; font-size: 1rem; color: #1d3557; }
.history { max-height: 120px; overflow-y: auto; margin-bottom: .5rem; }
.hist-item { font-size: .8rem; color: #444; padding: .1rem 0; border-bottom: 1px solid #eee; }
.hist-item:last-child { border-bottom: none; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1a5fa0; }

// Code not found

Each query answer eliminates huge swaths of possibility. With enough queries the attacker is left with a single candidate — the original secret. Notice that even exact query answers are enough: you do not need to hack anything, just do linear algebra. This is why the US Census Bureau redesigned its disclosure-avoidance system in 2020 after researchers showed that published tables could reconstruct individual records.

The Dinur-Nissim theorem states the precise trade-off:

• The setting: a private database of $n$ binary values. An analyst submits linear counting queries — each asks for the sum of some subset.
• The result: if the database answers more than $O(n \log n)$ queries each with error less than $\frac{\sqrt{n}}{2}$, an attacker can reconstruct all $n$ private values with high probability.
• Why: the queries form a system of linear equations. With enough equations the system has a unique solution — the secret database. Noise below the threshold is small enough to round away.
• The implication: there is a hard information-theoretic barrier. Accuracy $\times$ queries must stay below a budget, or reconstruction is inevitable.

This forced the field to accept that any useful statistical database leaks information, and the only question is how much. That shift in thinking led directly to differential privacy (Dwork, McSherry, Nissim, Smith — 2006), which adds calibrated random noise to each answer so that no single individual's data changes the output significantly. Rather than trying to hide the answer, differential privacy hides the contribution of each person.

The reconstruction theorem also exposed a weakness in the US Census: the 2010 decennial tables, when fed into a reconstruction algorithm, yielded accurate guesses for millions of Americans' age, sex, race, and ethnicity. The Census Bureau's response — the 2020 TopDown algorithm — is differential privacy at national scale.

Reconstruction attacks are not hypothetical — they have driven real policy changes:

• US Census 2020: the Census Bureau ran reconstruction experiments on the 2010 tables and found they could recover individual-level data for large fractions of the population. This triggered a shift to differential privacy for the 2020 release.
• Medical statistics: hospital aggregate reports (rates, averages, counts) can be combined to narrow down which patient has which condition — even without any database breach.
• Machine learning models: large language models and classifiers memorize training data. Membership-inference and model-inversion attacks are reconstruction attacks in disguise, targeting the model's weights instead of explicit query answers.
• Location data: publishing average commute times by neighborhood leaks enough signal to reconstruct individual home-to-work routes.

The fix in every case is the same: add carefully calibrated noise. The reconstruction theorem tells you exactly how much noise is the minimum necessary. Too little noise and reconstruction succeeds; too much and the statistics become useless. Differential privacy is the framework that hits the sweet spot — see also differential privacy and PAC learning for related trade-offs between information and leakage.

The database reconstruction theorem delivers an uncomfortable truth: there is no clever data-sharing scheme that gives accurate statistics and hides private records at the same time. Accuracy and privacy are not a matter of policy — they are in mathematical conflict.

The good news is that the theorem is also constructive: it tells you exactly what noise level is sufficient to prevent reconstruction. Differential privacy turns that lower bound into an engineering standard. The next time you read that a dataset was "anonymized" or "aggregated for privacy," the reconstruction theorem is the right lens: ask how many queries, how accurate, and whether enough noise was added — because without it, the answers themselves are the attack.