Is honeywords different from k-anonymity?

Question

Ari Juels and Ron Rivest propose a technqiue to strengthen password files called honeywords . Basically for each valid password they insert fake passwords (honeywords) and if somebody tries to bruteforce it can be detected .

The basic idea of obfuscating real data among fake data is crux of k-anonymity , l-diversity and other data privacy related concepts of data mining .

Any idea of honeywords is same as k-anonymity ? or are they two distinctly different ?

Answer 1

Actually, these concepts are conceptually quite different. I'm going to talk about $k$-anonymity, as $\ell$-diversity and $t$-closeness are related to $k$-anonymity, but can be seen as additional measures on top of $k$-anonymity that target homogeneous representation of the sensitive attribute’s values within a group and their relative frequencies respectively.

The idea of $k$ anonymity is, that you remove primary identifying information (such as names, ssn, etc.) from a table. But there are typically still so called quasi identifiers left (such as a combination of birthdate, zip and gender) which could be linked to external sources to allow identification if this anonymized table is linked to some external source (i.e., another table containing the same and additional attriutes).

So you have to make some assumptions about how this quasi identifier (i.e., the attribute combination) may look like. Having done this, you define a $k$ and you want that every unique value combination of values in the quasi identifier that appear in the table shows up at least $k$ times.

If this is initially not the case (which is very likely), then you apply attribute suppression (you remove the entire attribute if there is no chance of achieving the desired $k$) and generalization (you define a generalization hierarchy on the attribute and switch to the more generalized version, e.g, you have $ZIP="123456"$ -> $ZIP="12345*"$ and so on) until your $k$ is achieved. There is a bunge of algorithms to perform this task. Clearly, generalization is desirable, since you preserve more information.

Consequently, the main differences between these approaches are:

• In honeywords the data is assumed to be kept private, while you apply $k$-anonymity to data that is then made public, e.g., medical data for some statistical processing.
• In $k$-anonymity you work on a database (table data) where you remove unique identifiers before processing with $k$-anonymization (otherwise $k$-anonymity makes no sense), while in honeywords you have $(u_i,H(u_i)$ pairs and keeping the unique values $u_i$ (since the data is not made public).
• Honeywords introduces bogus data, while in $k$-anonymity you apply attributes suppression and generalization (on the original data) until you achieve your desired $k$).
• Honeywords is intended to detect something (brute forcing), but $k$ anonymization is a preventive measure before making something public (and is not intended to detect something).

Answer 2

In honeywords you "falsify" data with the intent of confusing the attacker. In k-anonymity you omit or merge data to do the same. If we were to disregard the different application scope for each, I'd say the two are pretty similar, but only in an abstract sort of way.

I suppose you could use honeydata in a k-anonymized dataset (in a statistically-neutral way), and wait to see if someone goes looking for mr. Fook Yu. That'd be fun.