When learning about cryptography and hashing, I remember seeing a concept where you could hash a number of values (ID's for example) and then validate against the hash, not storing the original IDs. Upon researching this further, I cannot find any concrete examples.

I am wondering if I misunderstood the concept when originally learning about hashing. Please review the following scenario and let me know if I misunderstood or the concept exists:

Concept

A university is running a contest for students. The university staff chose ten random student IDs as winners. Students can visit a website and enter their student ID to see if they won.

The winning student ID's are not stored in a database but rather are hashed. When a student enters an ID on the website, the ID entered is validated against this "winning hash."

Questions

  1. Is this type of "group of values" hashing and validation a concept that exists or did I misunderstand something in my research?
  2. If this does not exist, would the correct method be to hash each winning student ID, then when a student enters the ID to hash it and validate it against the individual stored hashes?

Thank you!

  • 1
    You could optimize the second approach by using a tree-based or hash-based set representation. – SEJPM Aug 9 at 15:27
  • 1
    Isn't a similar concept (with more safety guards for obvious reasons) used to store credit card information in online shops? – Aleksander Rassasse Aug 9 at 15:46
  • @AleksanderRassasse That was my thought but I'm not sure if the concept stores ALL card numbers in the same hash and validates it against the "big" hash or stores each numbers hash and validates against that. – Tom Aug 9 at 15:57
  • @SEJPM Sounds interesting, I'll pour more research into using something like that. Thank you! – Tom Aug 9 at 15:58
  • I think what you are looking for is the whole area of password hashing. The functionality is exactly what you are asking for. – mephisto Aug 10 at 9:53
up vote 1 down vote accepted

It sounds like you're describing a Bloom filter.

Note that they're designed to allow false positives (but not false negatives). They can be good to quickly check whether a value might be in a certain set worthy of a more computationally-expensive check. Imagine that you are scanning a large body of text word by word, there is a set of key words you're looking for, and there are more key words than fit in RAM. You can create a bloom filter out of all of the key words that fits in RAM. Whenever you find a word that passes the bloom filter, that means the word might be a key word, so you can then double-check the word against your list of key words on disk. This saves you from having to access the disk for every word you scan.

  • Invaluable as you've pointed me in the right direction. Thank you! – Tom Aug 10 at 13:45

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.