7

Does there exist any hashing algorithms suitable for comparing data that is similar but not exact matches?

For example one where similar input data generates a similar hash, with the difference in the hashes being proportional to the difference in the data.

All sensors have precision, accuracy, and noise specifications. In general such a hash could be useful for any type of authentication that relies on data from a sensor.

One example would be biometric identification. For example, two scans of the same finger or pictures of a face would be very similar but not exactly the same. Having this type of algorithm would allow an authentication service to store a hash rather than actual fingerprint or face data.

6
  • 1
    Perceptual hash
    – defalt
    Aug 7, 2021 at 6:12
  • 1
    Just wondering, what specific task are you trying to complete or would theoretically use this for? Sensors, Biometrics, and Images would all require vastly different methods. Aug 7, 2021 at 6:41
  • You'd probably want to use homomorphic encryption on your fingerprints.
    – Nat
    Aug 7, 2021 at 8:49
  • Such algorithms are sometimes called fuzzy hashes
    – nobody
    Aug 7, 2021 at 9:08
  • Do you work for Apple user4574 ;) ?
    – PaulG
    Aug 7, 2021 at 9:43

3 Answers 3

6

Generically this is referred to as Fuzzy Hashing.

How well this works can vary greatly upon the use and data.

Two fuzzy hashing algorithms I've used successfully in the past for various types of data are:

  • ssdeep - ssdeep is a program for computing context triggered piecewise hashes (CTPH). Also called fuzzy hashes, CTPH can match inputs that have homologies. Such inputs have sequences of identical bytes in the same order, although bytes in between these sequences may be different in both content and length.
  • deeptoad - DeepToad is a (python) library and a tool to clusterize similar files using fuzzy hashing techniques. This project was inspired by the well known tool ssdeep.

A clarification

You said, "...Having this type of algorithm would allow an authentication service to store a hash rather than actual fingerprint or face data..."

Normally biometric reference data is not stored as literal images. Rather it's stored as a subset of matching minutiae points. This allows both efficient storage as well as an implicit fuzzy search and match capability. This is critical with biometric data like fingerprints and face matching as a perfect match NEVER happens.

Depending upon your application, you may be trying to re-invent the wheel.

1
  • Weather a whole image is stored, minutiae, or some other processed sensor data, advantage of storing fuzzy hashes is that if someone steals a database of hashes for service X they shouldn't be able to use the hashes themselves to get into service X or any other service. Its the same advantage gained by storing a hash of a password rather than the password itself.
    – user4574
    Aug 7, 2021 at 23:57
1

For the pictures of faces example, you could try OpenCV's image hash comparison tool that looks for close enough. This is referred to as perceptual hashing and a good tutorial on this can be found at Image hashing with OpenCV and Python .

Fingerprints are compared by certain points extracted from the scan called minutiae (paper here for further reading) and then compared based on exacts not on "oh the readings are similar". You could potentially hash rough characteristics of the sensor data for comparison to give a more binary hash comparison, and store the actual accurate reading, however due to pre-image resistance design, where the hash is hard to mathematically derive from the original input, a minor change in a hash will affect the whole hash usually changing it completely.

1

tl;dr As quick-thoughts, you might generate a portfolio of hashes (instead of a single hash) for each fingerprint, such that you can check the contents of two different portfolios for overlap. Alternatively, homomorphic encryption.


I guess you could go in two directions:

  1. Use a portfolio of hashes.
    Generate a set of approximately-equal fingerprints, then hash each of them separately. Store all of the hashes in a portfolio; compare hashes in two portfolios to assess potential similarities.

  2. Use homomorphic encryption.
    Do normal fingerprint-comparison stuff, but using homomorphic encryption.


Option 1: Portfolio of hashes.

The basic idea is to:

  1. Round your fingerprints to a local approximation.

  2. Generate a portfolio that includes the local-approximation plus all close-enough-to-be-matching points.

  3. Hash each item in the portfolio separately.

For example, say you want to store a date (like someone's birth-date) and you want to hash it, but you want to be able to assess if another date is close after hashing. Then:

  1. Round the date its nearest coarse-grain approximation.

    • For example, if you approximate dates within 3 months and someone was born 2021-08-07, then round that to 2021-09-01.
  2. Generate a set of points about that rounded-value in each direction.

    • For example, if someone was rounded to 2021-09-01, then generate points for { 2020-09-01, 2020-12-01, [...], 2022-09-01 }.
  3. Hash each of the points, then forgot the original data. The set of hashes is now the hashed-fingerprint-portfolio.

Then to compare two hashed-fingerprint-portfolios, loop over each combination of fingerprints from each portfolio. For example:

public static bool AreMatching(
      Portfolio portfolio_A
    , Portfolio portfolio_B
  )
{
  foreach (var fingerPrint_A in portfolio_A)
  {
    foreach (var fingerPrint_B in portfolio_B)
    {
      if (fingerPrint_A == fingerPrint_B) { return true; }
    }
  }

  return false;
}

Conceptually, the fundamental problem is that cryptographic-hashes intentionally remove the ability to compare if two values are close, but we can still calculate the set of nearby points before hashing.

Then each fingerprint-hash encodes one local approximation that'd be considered a match.

2
  • As a thought: for dates, we could instead do more hashes over the local-domain, then truncate each of those hashes, even down to 1-bit-per-point. Then an approximation-check could involve looking for overlapping substrings.
    – Nat
    Aug 7, 2021 at 10:11
  • I like the idea of storing a family of hashes. The only major downside is that you need to store a hash for every possible combination of sensor values that could reasonably be expected given the accuracy and precision of the sensor (after rounding). The number of combinations would probably grow exponentially with the number of data points. Even so its a really good idea as long as the number of data points and number of values per point remains small enough.
    – user4574
    Aug 8, 2021 at 0:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .