[Cryptography] Homomorphic and Structured Encryption

Jerry Leichter leichter at lrw.com
Fri Feb 25 04:49:42 EST 2022

> Bloom filters are also used in spelling checkers.  The 'dictionary' of many spell checkers is a Bloom Filter which you can query to discover whether a word is, or is not, in the dictionary of known words.  It was the case early on that the Bloom Filter could be the only reference - the spell checker didn't have a database of the actual words anywhere.  The results were sometimes humorous because of that 'probabilistic' property, and you needed to make peace with the idea that your spell checker now thinks 'argingg' or something is a word because you added 'brownstone' to the dictionary.  Modern spell checkers actually have access to a list of words, and use Bloom Filters as a 'shortcut.'  They only look one up if the Filter is inconclusive.
A Bloom filter can't be inconclusive:  It always returns a Boolean - found/not found.  A "not found" answer is guaranteed correct; a "found" answer is probabilistic.  You could go ahead and do a full check in the latter case, but for a spelling checker - where most words are actually correct - that wouldn't make a lot of sense.

Use cases where you expect most things not to be in the database don't seem to be common.  Years ago, David Wittenberg and I got a patent (long expired) on using a Bloom filter with cryptographic hash functions to test whether proposed password was already in use by anyone in a system.  Because of the cryptographic hashes, it would be impractical to determine what passwords were actually in use.  This is a case where you expect most of the answers to be "not found."  However, checking the "found" items would require keeping the actual passwords around, which you don't want to do. But ... that could be used if you were checking for matches to *leaked* passwords, I suppose.
                                                        -- Jerry

More information about the cryptography mailing list