up:: Security Basics MOC
De-Identification, Re-Identification, and Linkage Keys
De-identification is the process of removing or transforming the elements of a dataset that identify the people in it, so the result can be used or shared without being treated as personal information. Re-identification is the reverse, whether performed deliberately by the original holder or reconstructed by an outsider from other data. A linkage key is the secret that makes deliberate reversal possible: a code assigned to each record so the holder can reconnect the de-identified data to the person it came from. That key is a cryptographic asset with a full lifecycle, it is usually managed by a data team rather than a security team, and it is almost never recorded in any inventory of an organization’s cryptography.
The short version:
- De-identified data sits on a spectrum rather than a boundary, and the reversibility of a dataset depends on what the holder kept, not on the label applied to the file.
- A linkage key is a genuine cryptographic secret. Whoever holds it can turn the de-identified dataset back into identified records.
- NIST states plainly that “hashing without a key generally does not confer security because an attacker can brute force all possible values to be hashed,” which rules out the most common implementation.
- The HIPAA rule that permits a re-identification code requires that the code is not derived from information about the individual and that the mechanism stays undisclosed, which describes a keyed construction with a protected key.
- Re-identification by an outsider is a separate risk running on a separate clock, and it gets easier over time as auxiliary datasets accumulate.
An everyday analogy
A hospital sends a research file to an analytics partner with every name stripped out and a serial number in place of each patient. The partner sees numbers. The hospital keeps a single spreadsheet mapping each serial number back to a medical record number, locked in a drawer. The file at the partner is only as anonymous as that drawer, and nobody in either organization thinks of the drawer as cryptography, which is why nobody audits the lock.
What is de-identification?
De-identification is a transformation applied to a dataset so that the individuals in it cannot reasonably be identified from the data alone. In the United States, the health-sector version has a precise regulatory definition. Under 45 CFR 164.514(a), “health information that does not identify an individual and with respect to which there is no reasonable basis to believe that the information can be used to identify an individual is not individually identifiable health information,” which is the sentence that removes the data from the scope of the HIPAA Privacy Rule.
Source: eCFR, “45 CFR 164.514, Other requirements relating to uses and disclosures of protected health information,” ecfr.gov.
The regulation then supplies two ways to get there, and they are very different instruments.
How do the two de-identification standards differ?
| Dimension | Expert Determination, 164.514(b)(1) | Safe Harbor, 164.514(b)(2) |
|---|---|---|
| What it requires | a person with appropriate knowledge of statistical and scientific principles determines the risk is very small | removal of 18 enumerated categories of identifier |
| Basis of the judgment | risk that the information could be used, alone or with other reasonably available information, by an anticipated recipient | a fixed list, applied mechanically |
| Documentation | the methods and results of the analysis must be documented | no analysis required, removal is the test |
| Handles auxiliary data | yes, explicitly, because the standard names combination with other information | no, the list is fixed regardless of what else exists |
| Dates | may be retained where the analysis supports it | all date elements except year are removed, and ages over 89 are aggregated |
| Geography | may be retained where the analysis supports it | nothing smaller than a state, except a 3-digit zip prefix where the area holds more than 20,000 people |
| Residual obligation | none beyond the determination | the entity must not have actual knowledge that the data could still identify someone |
| Typical failure | an analysis that underestimates what an anticipated recipient can obtain | a dataset that passes the list and remains re-identifiable through combinations the list does not cover |
Source: eCFR, “45 CFR 164.514(b),” ecfr.gov.
The 18-item Safe Harbor list is worth reading in full at least once, because its last entry is the one that governs linkage keys. After names, geography, dates, telephone and fax numbers, email addresses, Social Security numbers, medical record numbers, health plan beneficiary numbers, account numbers, certificate and license numbers, vehicle and device identifiers, URLs, IP addresses, biometric identifiers and full-face images, the list closes with “any other unique identifying number, characteristic, or code, except as permitted by paragraph (c) of this section.” Paragraph (c) is the linkage-key provision.
What is a linkage key?
A linkage key is the code that lets the original holder reverse a de-identification. The HIPAA text describes the whole construct in two sentences. A covered entity “may assign a code or other means of record identification to allow information de-identified under this section to be re-identified,” provided that the code “is not derived from or related to information about the individual and is not otherwise capable of being translated so as to identify the individual,” and that the entity “does not use or disclose the code or other means of record identification for any other purpose, and does not disclose the mechanism for re-identification.”
Source: eCFR, “45 CFR 164.514(c), Implementation specifications, Re-identification,” ecfr.gov.
Read as an engineer rather than as a lawyer, that paragraph specifies a cryptographic construction. The code has to be unlinkable to the individual by anyone who does not hold the secret, which rules out anything computed openly from the person’s own attributes. The mechanism has to stay undisclosed, which makes it a secret with a lifetime, an owner and a compromise mode. What the regulation describes, without naming it, is a keyed pseudonym.
The same object appears under other names across other regimes and industries: a pseudonymization key, a token vault, a tokenization secret, a hashing salt in the loose usage, a crosswalk table, a subject identifier map. The engineering question is identical in every case. Somebody holds a secret, and whoever obtains it converts an entire de-identified dataset back into an identified one in a single step.
Why is an unkeyed hash not a linkage key?
Because the input space of a real-world identifier is small enough to search exhaustively, and NIST says so in as many words. SP 800-188 states that “hashing without a key generally does not confer security because an attacker can brute force all possible values to be hashed.”
Source: NIST, “SP 800-188, De-Identifying Government Data Sets,” September 2023, csrc.nist.gov.
This is the single most common implementation error in the category. A team replaces a medical record number or a Social Security number with SHA-256 of that value, observes that the output looks like random hex, and treats the result as anonymous. The hash function is working correctly. The problem is that the attacker computes the same function: every 9-digit Social Security number can be hashed in bulk, every medical record number in a known format can be enumerated, and the resulting table converts the “anonymous” column back to identifiers by lookup. The output is not a secret, because the input was never secret enough to protect it.
The compliant construction is a keyed one. SP 800-188 describes hashing with a keyed hash, “a special kind of hash function that produces different hash values for different keys,” and specifies that “the hash key should have sufficient randomness to defeat a brute force attack aimed at recovering the hash key (e.g., SHA-256 HMAC with a 256-bit randomly generated key).” It adds that the key “should be secret and should be discarded unless there is a desire for repeatability,” and that where repeatability is wanted, the key “should be stored in a secure location that is separate from the de-identified dataset.”
Source: NIST, “SP 800-188, De-Identifying Government Data Sets,” section 4.3.1, csrc.nist.gov.
That construction is an HMAC, which is a message authentication code being used here as a pseudonym generator rather than as an authenticator, and its security rests entirely on the key.
What does NIST say about the risks of this whole approach?
More than most practitioners expect, and section 4.3.2 of SP 800-188 is titled “Special Security Note Regarding the Encryption or Hashing of Direct Identifiers” for a reason. It observes that the transformation of direct identifiers through encryption or hashing “carries special risks, as errors in procedure or the release of the key used in the encryption or hashing operation can compromise identities for the entire dataset,” and adds a line that deserves to be quoted at every design review: “there is no way to verify that a key has not been released.”
The section closes harder than the regulation does. “Because encryption may be reversed and both approaches may be the subject of a successful brute force attack, the use of encryption or hashing to protect direct identifiers is not recommended.”
Source: NIST, “SP 800-188, De-Identifying Government Data Sets,” section 4.3.2, csrc.nist.gov.
The tension between the two documents is real and worth stating clearly. The HIPAA rule permits a re-identification code and sets conditions on it. NIST recommends against relying on encryption or hashing of direct identifiers at all, on the grounds that the failure is catastrophic and undetectable. Both are current. An organization operating a linkage key is doing something the regulation allows and the relevant NIST guidance advises against, and most teams doing it have never seen the second document.
Why does the linkage key never appear in a cryptographic inventory?
Because of who owns it. A linkage key is created by a data engineering, analytics or research team to solve a data problem, it lives in a pipeline configuration or a secrets store attached to that pipeline, and it is understood internally as a data-processing detail. A cryptographic bill of materials assembled from application code, TLS endpoints and certificate stores does not reach it, because nothing about it looks like a certificate or a handshake.
The result is a key with several properties that would be alarming if anyone stated them together. It protects the identity of every person in the dataset rather than a single record. It is long-lived, because rotating it breaks the linkage it exists to provide, so the usual rotation discipline works directly against the function. Its compromise is silent, per the NIST observation above. And it commonly exists in more than one copy, because the pipeline that generates pseudonyms and the process that reverses them are frequently different systems.
That combination is what makes it worth naming as its own asset class in cryptographic discovery rather than leaving it to be found by accident.
How reliably can de-identified data be re-identified by an outsider?
Far more reliably than the intuition of most data owners suggests, and the foundational demonstration is now old enough to be uncontroversial. Narayanan and Shmatikov applied a statistical de-anonymization method to the Netflix Prize dataset, which contained anonymous movie ratings from 500,000 subscribers, and reported that “with 8 movie ratings (of which 2 may be completely wrong) and dates that may have a 14-day error, 99% of records be uniquely identified in the dataset. For 68%, two ratings and dates (with a 3-day error) are sufficient.”
Source: Arvind Narayanan and Vitaly Shmatikov, “Robust De-anonymization of Large Datasets (How to Break Anonymity of the Netflix Prize Dataset),” arXiv:cs/0610105, arxiv.org.
The mechanism generalizes past movie ratings. High-dimensional records about individual behavior are close to unique per person, so a small amount of outside knowledge about one person locates their record. Health data is high-dimensional in exactly this way, since a sequence of diagnosis codes, procedure dates and visit locations describes a person as distinctively as a rating history does.
This is the risk the Expert Determination standard is built to reason about, since its test is explicitly about combination “with other reasonably available information.” It is also the risk that gets worse with time and with no action by the data holder, because what is reasonably available grows every year. A determination describes the risk at the moment it was made.
How does the quantum threat reach de-identified data?
Along three distinct paths, and separating them prevents both complacency and overstatement.
- The linkage key itself is comparatively robust. An HMAC-SHA-256 pseudonym key is symmetric, so Grover’s algorithm reduces its effective strength rather than breaking the construction, and a 256-bit key retains a substantial margin. The cryptography of the pseudonym is the strongest part of the arrangement.
- What surrounds the key is the exposure. Linkage keys are transported, wrapped, escrowed and backed up, and those operations commonly use public-key cryptography that Shor’s algorithm does break. A symmetric key wrapped under a quantum-vulnerable mechanism inherits that vulnerability, which is the general pattern described in key management.
- The data lives long enough for harvest-now-decrypt-later to apply. Health and research records carry confidentiality lifetimes measured against a human lifespan, which is the condition Mosca’s theorem identifies as making harvesting a present-day concern rather than a future one.
Running underneath all three is the non-cryptographic clock. Re-identification through auxiliary data needs no key and no quantum computer, and it improves steadily as more datasets become available. For most de-identified holdings that clock is the faster of the two.
Common misconceptions
- “De-identified means anonymous.” De-identification is a property of a dataset relative to what else exists in the world, and the Expert Determination standard says so by testing against other reasonably available information.
- “Hashing the identifier makes it safe.” NIST states that hashing without a key generally confers no security, because the attacker can hash every possible input.
- “A salt fixes it.” A salt stored beside the data, or derived per record, does not create a secret. What supplies security is a key that is random, secret, and kept separate from the dataset.
- “The linkage key is a data engineering concern.” It is a cryptographic key whose compromise re-identifies every record at once, and it has the same lifecycle obligations as any other key of that reach.
- “If we never re-identify, the key does not matter.” A key that exists can be stolen, and NIST notes there is no way to verify that a key has not been released.
- “Safe Harbor removal makes a dataset permanently de-identified.” Safe Harbor is a fixed list applied at a moment in time, and it makes no claim about combinations with datasets that appear later.
Questions people ask
What is the difference between de-identification and pseudonymization? Pseudonymization replaces an identifier with a stand-in while retaining the ability to reverse the substitution, so the data remains linkable by whoever holds the secret. De-identification is the broader goal of making the individual unidentifiable, and it may or may not preserve a reversal path.
Is a linkage key a cryptographic key? Yes, whenever it is generated by a keyed construction such as HMAC, and functionally yes even when it is a lookup table, because it is a secret whose disclosure re-identifies the dataset. The lookup-table version has the same blast radius and none of the cryptographic hygiene.
Does HIPAA require a linkage key to be protected in a specific way? The regulation states the conditions rather than the mechanism. The code must not be derived from or related to information about the individual, must not be capable of being translated to identify the individual, must not be used or disclosed for any other purpose, and the mechanism for re-identification must not be disclosed.
Why would NIST advise against a technique the regulation permits? They address different questions. The regulation sets the conditions under which data leaves the scope of the Privacy Rule. NIST SP 800-188 assesses the engineering risk, and concludes that the failure mode of a compromised key is total and undetectable.
Who typically holds the linkage key? In practice the team that built the de-identification pipeline, which is usually a data engineering, analytics or research function rather than a security function. That ownership is the main reason the key is missing from most cryptographic inventories.
Does rotating the linkage key help? Rotation breaks the linkage the key exists to provide, so a rotated key produces pseudonyms that fail to match the historical dataset. This tension is intrinsic to the design and is why these keys tend to be among the longest-lived secrets an organization holds.
Can de-identified data be re-identified without any key at all? Yes, through combination with outside datasets, which is the result the Netflix Prize work demonstrated. That path requires no cooperation from the data holder and no access to any secret.
Does a limited data set count as de-identified? No. A limited data set under 164.514(e) is protected health information with certain direct identifiers excluded, and it remains subject to the Privacy Rule under a data use agreement. It is a distinct category from de-identified data.
Is this only a healthcare problem? No. The same construct appears wherever records are shared in pseudonymous form, including advertising identifier graphs, financial tokenization, telemetry pipelines and longitudinal research, and the key has the same properties in every one of them.
Everything here is the map, given freely. When your team needs the keys that reverse its own de-identification found, inventoried and governed alongside the rest of its cryptography, that’s the work I do.
Last verified 2026-09-03 · Maintained by Addie LaMarr, LaMarr Labs.