Introduction

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.

Reconstruct the Secret

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.

<!-- reconstruction attack demo layout -->
<p class="hint">A secret 6-bit vector is hidden. Pick which positions to include in a <b>sum query</b>, then click Ask. Each exact answer eliminates candidates until only the secret remains — no hacking required, just linear algebra.</p>
<div class="panel">
  <div class="secret-row">
    <span class="label">Secret vector:</span>
    <div id="secret-display" class="bit-row hidden-bits"></div>
    <button id="reveal-btn" type="button" class="ghost small">Show secret</button>
  </div>
  <div class="candidates-row">
    <span class="label">Remaining candidates:</span>
    <span id="cand-count" class="count-badge">64</span>
  </div>
</div>
<div class="query-panel">
  <p class="query-label">Select positions to sum (x1 … x6):</p>
  <div id="query-checkboxes" class="query-bits"></div>
  <div class="query-row">
    <button id="ask-btn" type="button">Ask query</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">Best next query</button>
  <button id="reset-btn" type="button" class="ghost">New secret</button>
</div>
<div id="status" class="status"></div>

/* styles for the reconstruction attack demo */
* { 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; }

// Reconstruction attack demo: a secret binary vector is chosen at random.
// Each linear query returns the exact sum of chosen positions.
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

const N = 6; // number of private bits
// the private database — one random bit per entry
const SECRET = Array.from({ length: N }, () => Math.random() < 0.5 ? 1 : 0);

// all 2^N possible vectors — start with full uncertainty
let candidates = [];
for (let mask = 0; mask < (1 << N); mask++) {
  const v = Array.from({ length: N }, (_, i) => (mask >> i) & 1);
  candidates.push(v);
}

// which positions the current query includes
const queryMask = Array(N).fill(false);
let revealed = false;
let queryCount = 0;

// DOM refs
const secretDisplay = document.getElementById('secret-display');
const candCount = document.getElementById('cand-count');
const queryCheckboxes = document.getElementById('query-checkboxes');
const queryResult = document.getElementById('query-result');
const history = document.getElementById('history');
const status = document.getElementById('status');

function renderSecret() {
  // show each bit, or a question mark if still hidden
  secretDisplay.innerHTML = '';
  SECRET.forEach((b, i) => {
    const d = document.createElement('div');
    if (revealed) {
      d.className = 'bit bit-' + b;
      d.textContent = b;
    } else {
      d.className = 'bit bit-hidden';
      d.textContent = '?';
    }
    secretDisplay.appendChild(d);
  });
}

function renderQueryBits() {
  // render the toggle buttons for building a query
  queryCheckboxes.innerHTML = '';
  for (let i = 0; i < N; i++) {
    const d = document.createElement('div');
    d.className = 'qb' + (queryMask[i] ? ' selected' : '');
    d.textContent = 'x' + (i + 1);
    d.title = i18nFmt('Include position %i% in the query sum', { i: i + 1 });
    d.addEventListener('click', () => {
      queryMask[i] = !queryMask[i];
      renderQueryBits();
    });
    queryCheckboxes.appendChild(d);
  }
}

function updateCandCount() {
  // update the candidate counter and highlight when solved
  candCount.textContent = candidates.length;
  if (candidates.length === 1) {
    candCount.classList.add('solved');
  } else {
    candCount.classList.remove('solved');
  }
}

function askQuery() {
  // ask the selected linear query and filter candidates
  const indices = queryMask.map((on, i) => on ? i : -1).filter(i => i >= 0);
  if (indices.length === 0) {
    status.textContent = 'Select at least one position.';
    status.className = 'status info';
    return;
  }
  const answer = indices.reduce((s, i) => s + SECRET[i], 0);
  queryCount++;
  // keep only candidates consistent with the answer
  const before = candidates.length;
  candidates = candidates.filter(v => indices.reduce((s, i) => s + v[i], 0) === answer);
  const after = candidates.length;

  const mask_label = indices.map(i => 'x' + (i + 1)).join('+');
  queryResult.textContent = i18nFmt('%mask% = %ans%', { mask: mask_label, ans: answer });

  // add a line to the query history
  const item = document.createElement('div');
  item.className = 'hist-item';
  item.textContent = i18nFmt('Q%n%: %mask% = %ans%  (%before% → %after% candidates)', { n: queryCount, mask: mask_label, ans: answer, before: before, after: after });
  history.prepend(item);

  updateCandCount();

  if (candidates.length === 1) {
    revealed = true;
    renderSecret();
    status.textContent = i18nFmt('Reconstructed in %n% queries!', { n: queryCount });
    status.className = 'status ok';
  } else {
    status.textContent = i18nFmt('%n% candidates remain.', { n: candidates.length });
    status.className = 'status info';
  }
}

function autoQuery() {
  // choose the query that maximally splits the remaining candidates
  // (greedy: minimise the largest bucket after the query)
  if (candidates.length === 1) {
    status.textContent = 'Secret already reconstructed.';
    status.className = 'status ok';
    return;
  }
  // try every non-empty subset as a potential query mask
  let bestMask = null, bestScore = -1;
  for (let mask = 1; mask < (1 << N); mask++) {
    const idx = Array.from({ length: N }, (_, i) => (mask >> i) & 1 ? i : -1).filter(i => i >= 0);
    // bucket candidates by their answer to this query
    const buckets = {};
    for (const v of candidates) {
      const s = idx.reduce((a, i) => a + v[i], 0);
      buckets[s] = (buckets[s] || 0) + 1;
    }
    const largest = Math.max(...Object.values(buckets));
    const score = candidates.length - largest;
    if (score > bestScore) { bestScore = score; bestMask = mask; }
  }
  for (let i = 0; i < N; i++) queryMask[i] = !!((bestMask >> i) & 1);
  renderQueryBits();
  askQuery();
}

function reset() {
  // pick a fresh secret and reset all state
  candidates = [];
  for (let mask = 0; mask < (1 << N); mask++) {
    const v = Array.from({ length: N }, (_, i) => (mask >> i) & 1);
    candidates.push(v);
  }
  queryMask.fill(false);
  revealed = false;
  queryCount = 0;
  queryResult.textContent = '';
  history.innerHTML = '';
  status.textContent = '';
  status.className = 'status';
  renderSecret();
  renderQueryBits();
  updateCandCount();
  candCount.classList.remove('solved');
}

document.getElementById('reveal-btn').addEventListener('click', () => {
  revealed = !revealed;
  renderSecret();
  document.getElementById('reveal-btn').textContent = revealed ? 'Hide secret' : 'Show secret';
});
document.getElementById('ask-btn').addEventListener('click', askQuery);
document.getElementById('auto-btn').addEventListener('click', autoQuery);
document.getElementById('reset-btn').addEventListener('click', reset);

renderSecret();
renderQueryBits();
updateCandCount();
Result
Console

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 Real Complexity

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

  • The setting: a private database of nn 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(nlog⁡n)O(n \log n) queries each with error less than n2\frac{\sqrt{n}}{2}, an attacker can reconstruct all nn 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/reconstruction-attacks/Content licensed under CC BY-NC 4.0.