Information Anonymization – Historical past and Key Concepts

By Nicolas Sartor, Aircloak.

“’Anonymized’ Data Can Be Anything But’” – Forbes, July 24, 2019

When the world media reported the outcomes of a current scientific paper on the ineffectiveness of information anonymization, it was something however information.

  • Already in 1981, the US laptop scientist Dorothy E. Denning said in one in every of her scientific papers on database safety that when working with knowledge, it could actually most likely by no means be fully ensured that no delicate info is revealed.
  • In 2008, scientists Arvind Naranayan and Vitaly Shmatikov revealed their work on the now-infamous Netflix de-anonymization case. The researchers succeeded in re-identifying a supposedly nameless knowledge set launched by Netflix. And the headlines? “Why ‘Anonymous’ Data Sometimes Isn’t”.
  • In August 2009, Paul Ohm’s paper “Broken Promises of Privacy: Responding to the Surprising Failure of Anonymization”was revealed. His sober conclusion was: “Data can be either useful or perfectly anonymous but never both.”

It appears as if historical past repeats itself always. And this raises a giant query:

Why, after many years of intensive analysis and 1000’s of scientific publications, has no knowledge anonymization expertise that’s usually usable by non-experts been developed to date?

Timeline on the historical past of information anonymization.

As a way to reply this query, we have to delve into the previous. Allow us to take a look at the event of anonymization in a broad context. This historical past touches on analysis, enterprise, politics, and public opinion, in addition to arithmetic, statistics, info expertise, ethics, and sociology. Above all, it’s characterised by a everlasting battle:

The fixed stress between knowledge safety and knowledge high quality.


Privateness vs. Utility Commerce-off: The higher the information utility must be, the more severe will get the privateness and vice versa.

The Beginnings of Information and Confidentiality

One of many first establishments to make use of knowledge on a big scale was the US Federal Bureau of Statistics (Census Bureau). In the beginning of the 19th century, censuses have been performed at common intervals to find out how seats within the Home of Representatives wanted to be redistributed, what taxes might be levied on every state, and what the nation’s army potential was within the occasion of struggle.

Throughout this time, knowledge safety hardly performed a job. The primary 50 years of census taking is notable for the absence of concern about privateness. This modified round 1850 when census questions elevated in each quantity and diploma of sensitivity. As a safety measure, the Census Bureau started to take away private knowledge from publicly out there census knowledge.

Over the following many years, the bureau used a wide range of strategies to mitigate the danger of people being recognized within the launched knowledge. These strategies embody rounding, including random noise to values, aggregation, cell suppression, cell swapping, and sampling, amongst others.

Within the 1950s, the bureau began utilizing computer systems to tabulate knowledge, and by the 1960s, anonymization strategies like these talked about above have been being automated. Computer systems enabled analysts to “cross-tabulate” knowledge (set filter situations on queries). This tremendously elevated an analyst’s potential to research the information but in addition opened the likelihood that an analyst might specify a question that uniquely identifies a person.

One of many first computer systems that was utilized by the US Census for automated statistics: UNIVAC I (Credit score:

The talk on knowledge safety began within the early 1960s. The US authorities underneath John F. Kennedy deliberate to arrange a Nationwide Information Centre to additional enhance the state info system. The general public considered this as heavy interference within the constitutional “Right to be alone” and “Right to privacy.” The venture failed and triggered calls for for a authorized foundation for the processing of non-public knowledge. The eventual consequence was the adoption of the Privateness Act in 1974, which launched guidelines for knowledge processing for federal authorities containing the important ideas of information safety: Necessity, Safety, and Transparency.

The American debate was repeated in Europe. In 1970, the Hessian Information Safety Act was launched, thought to be the oldest knowledge safety legislation on the earth. It regulated when the general public administration of the German State of Hesse could course of private knowledge and which necessities it should observe in doing so.  Based mostly on the general public discussions about knowledge safety, analysis into anonymization was additionally intensified. This was the start of a cycle that also persists:

Initially, solely easy knowledge is revealed. However over time, more and more refined knowledge is launched. To safe that knowledge, new anonymization strategies are invented, however every time researchers discover a technique to bypass them.

One idea that promised to deal with higher complexity and knowledge variety was the addition of noise. The earliest publication we discovered that proposes including noise is from the statistician, Fellegi, in 1972. In fact, noise should be unpredictable and, subsequently random. Within the context of a query-based system, this creates an issue. If every reply produced has a brand new zero-mean random noise pattern, then an analyst want solely repeat the question a number of occasions and take the typical to get rid of the noise.

Researcher Dorothy E. Denning proposed seeding the random quantity generator with the contents of the question itself. However even she acknowledged that this method was straightforward to interrupt.

Noisy Information (Credit score:

Denning by no means explored this downside additional and stopped engaged on knowledge anonymity altogether. In truth, by the mid-1980s, your complete laptop science neighborhood had misplaced curiosity in knowledge anonymity. That was partly as a result of it was a troublesome downside, however primarily as a result of the analysis neighborhood had much more urgent issues to work on.

The Renaissance of Information Anonymization

Quick ahead round 15 years, and knowledge anonymization turns into a sizzling matter in Pc Science once more. In 1997, Latanaya Sweeney managed to re-identify the then Massachusetts Governor William Weld from supposedly ‘anonymized’ well being knowledge. In his paper “Broken Promises of Privacy,” College of Colorado legislation professor Paul Ohm describes the case.

“At the time the Massachusetts Group Insurance Commission (GIC) released the data, William Weld, then Governor of Massachusetts, assured the public that GIC had protected patient privacy by deleting identifiers. In response, then graduate student Sweeney started hunting for the Governor’s hospital records in the GIC data. She knew that Governor Weld resided in Cambridge, Massachusetts, a city of 54,000 residents and seven ZIP codes. For twenty dollars, she purchased the complete voter rolls from the city of Cambridge, a database containing, among other things, the name, address, ZIP code, birth date, and sex of every voter. By combining this data with the GIC records, Sweeney found Governor Weld with ease. Only six people in Cambridge shared his birth date, only three of the men, and of them, only he lived in his ZIP code. In a theatrical flourish, Dr. Sweeney sent the Governor’s health records (which included diagnoses and prescriptions) to his office.”

Latanaya Sweeney and William Weld (Credit score: and

Sweeney’s outcomes had a major impression on privacy-centered policy-making together with the well being privateness laws HIPAA, however she additionally launched the formal Ok-Anonymity mannequin to beat the shortcomings of older anonymization strategies. The mannequin was subsequently enhanced by additions known as ℓ-Variety and t-closeness. Researchers and analysts moved a step nearer to the objective of having the ability to analyze knowledge in a privacy-preserving means. Sadly, producing the anonymized knowledge and balancing it with affordable utility was nonetheless a really advanced guide course of and error-prone.

In consequence, in lots of sensible purposes, the power of anonymization was sacrificed in favor of upper knowledge usability. This method even had authorized backing. The 1974 German Federal Information Safety Act outlined anonymization as follows:

“Anonymization is the alteration of non-public knowledge […] in order that the person details about private or factual circumstances can now not be attributed to an recognized or identifiable pure individual, or can solely be attributed with a disproportionately massive expenditure of time, price and labor.

Attributable to this wording, the time period “factual anonymization” was coined. It was already clear at the moment that no anonymization process can assure privateness. So, the disclosure of delicate info couldn’t fully be excluded within the case of “factual anonymization,” however it required a disproportionately massive effort on the a part of an attacker.

The “disproportionality” was largely decided by financial facets however was not outlined exactly. It was in a authorized gray space – there was neither an official authority that might verify anonymization processes nor authorized penalties for inadequate anonymization.

A Manner out of the Dilemma…?

In 2006 the supposed “Game Changer” was launched. Cynthia Dwork of Microsoft Analysis revealed a paper on an idea known as ‘Differential Privacy’. Just like Ok-Anonymity, Differential Privateness just isn’t an anonymization methodology, however a mathematical mannequin of privateness. Nonetheless, the groundbreaking information was that you might now calculate, and thus formally show, how nameless an individual was in an information report. Researchers, practitioners, and attorneys have been (and nonetheless are) extraordinarily impressed by this mannequin.

Through the years that adopted, the analysis neighborhood and most people grew to become more and more satisfied that differential privateness is the one resilient idea that may supply a means out of the privateness vs. utility dilemma.

It took one other eight years for the speculation to be put into apply. In 2014, Google started to gather differential non-public person statistics in Chrome. Two years later, Apple adopted go well with and used differential privateness for person knowledge from iPhones. However once more it didn’t take lengthy to get again to the well-known downside of utility vs. privateness.

Differential Privateness turns into a factor – Google Traits for ‘Differential Privacy” since 2004 with a spike in 2016, resulting from Google’s and Apple’s implementation.

Differential Privateness makes use of a parameter known as epsilon to find out the diploma of privateness. To ensure that knowledge to be protected, this parameter should stay very low. Epsilon straight limits the variety of queries you can also make. A knowledge set with a low (and safe) epsilon < 1 can solely be queried just a few occasions (often round just a few 10s of queries in whole). After that, entry to the information is now not permitted, as privateness can’t be assured.

The Wired article “How One of Apple’s Key Privacy Safeguards Falls Short” highlights the issue:

“[…] the analysis crew decided that MacOS’s implementation of differential privateness makes use of an epsilon of 6, whereas iOS 10 has an epsilon of 14. As that epsilon worth will increase, the danger that a person person’s particular knowledge might be ascertained will increase exponentially.

“According to differential privacy co-inventor McSherry, academics generally see any value of epsilon over one as a serious privacy compromise. iOS and macOS send that data back to Apple once a day; McSherry says the risk increases with every day’s upload. “Anything much bigger than one is not a very reassuring guarantee,” McSherry says. “Using an epsilon value of 14 per day strikes me as relatively pointless as a safeguard”.

Many different differential privateness implementations share this downside. Largely, when making an attempt to protect knowledge usability, a a lot greater epsilon is chosen, and knowledge safety is sacrificed.

Google’s recently released open-source library, which is designed to permit analysts around the globe to make use of differential privateness, additionally offers customers a free hand in selecting the epsilon:

“Epsilon is a configurable parameter. A lower value means more privacy but less accuracy.”

The approaching months will present how successfully Google’s open-source library for Differential Privateness is utilized in apply. The worry stays that customers will resolve in favor of excessive knowledge usability and in opposition to knowledge safety, as already proven prior to now when coping with different anonymization strategies.

Sacrificing the Good for the Excellent

In 2005, German statistics professor Rainer Lenz coined the time period “data protection idealist” to explain one of many greatest issues in statistics and knowledge anonymization: the discrepancy between concept and apply.

“…the case of the data protection idealist can […] not be considered relevant. Rather, it represents a special case in which […] the attacker is not interested about the value of the information that is […] revealed by him, but by showing that deanonymization […] is possible. A data protection idealist will accept much higher costs because disclosure as such is important to him. This cost-benefit relation is outside of the reasonable framework and therefore, cannot be considered.”

If the previous many years have proven us something, it’s that excellent and usable anonymization doesn’t exist. The use instances are too completely different, the technical progress too quick, the IT infrastructures too heterogeneous, and the questions in analyses too advanced for any theoretical mannequin to be transferred into apply.

(Credit score:

In fact, it’s troublesome to persuade an awesome majority of researchers, attorneys, and different specialists that even differential privateness just isn’t the magic bullet that has been claimed. It could take years for the general public picture of a “data protection ideal” and the perspective in the direction of “perfect data anonymization” to alter once more.

Who’s it accountable? Privateness and private knowledge are extremely emotive points. No person needs their very own info, reminiscent of affected person recordsdata or financial institution transaction knowledge to be made public. Furthermore, in response to knowledge safety researchers Arvind Naranayan and Vitaly Shmatikov, the issue lies not only in the individual case but also in social dimensions:

“We have also come to better recognize that these aggregations of data may result in harms to society and democracy, rather than just to individuals, as illustrated by Cambridge Analytica’s activities.”

Breaking the Age-Outdated Cycle of Nonsense

However how can we forestall ourselves from persevering with to go spherical in circles or from fully freezing given the complexity of the issue?

Our (quick) reply is absolute transparency and steady improvement.

After we based Aircloak in 2014, we set the objective of changing the gradual and error-prone processes of anonymizing knowledge with an automatic resolution. We depend on an empirical slightly than a proper method, which is basically primarily based on 4 ideas:

  • Use robust standards for anonymity
  • Set up and keep a “no known attacks” stance
  • Full transparency
  • Encourage lively public oversight

We settle for that no usable type of anonymization offers a full assure. To make sure that Aircloak stays state-of-the-art always and complies with the anonymization requirements of GDPR, we’ve got launched the world’s solely bug bounty for an anonymization methodology with the Aircloak Attack Challenge. We encourage privateness specialists to check and assault our anonymization. Any vulnerabilities which might be recognized in our software program are instantly investigated, and we launch a patch as quickly as doable.

This ensures that our prospects can depend on a really excessive diploma of anonymization, whereas their knowledge stays usable with none want for knowledgeable information.

Yves-Alexandre de Montjoye, Assistant Professor of Information Safety at UCL London and a member of the Belgian knowledge safety supervisory authority, additionally means that Privacy Enhancing Technologies should take a proven model from IT-Security: the adversarial approach.

“For the researchers, the important thing takeaway from the work is change of mindset is required round privateness safety akin to the shift the safety trade underwent in transferring from sitting behind a firewall ready to be attacked to adopting a pro-active, adversarial method that’s meant to out-smart hackers.

“As a community to really move to something closer to adversarial privacy,” de Montjoye tells TechCrunch. “We have to begin adopting the pink crew, blue crew penetration testing that has turn out to be customary in safety.

“At this point it’s unlikely that we’ll ever find a perfect system, so I think what we need to do is how do we find ways to see those vulnerabilities, patch those systems and really try to test those systems that are being deployed — and how do we ensure that those systems are truly secure?”

We’re, subsequently, very grateful when third events have interaction in our resolution by the Assault Problem and assist to make it safer. We imagine that the moral and accountable use of delicate info is unquestionably doable and hope that Aircloak Insights contributes to that objective.


Original. Reposted with permission.


About the Author

Leave a Reply

Your email address will not be published. Required fields are marked *