[Cryptography] Homomorphic and Structured Encryption

[Ray Dillinger]

On 2/23/22 17:49, Joshua Marpet wrote:
> I was asked if anyone has performed/built commercially viable
> implementations/products using homomorphic encryption and/or
> structured encryption.
>
> I found Tripleblind and I'm still trying to get a technical deep dive
> with them.
>
> But! Does anyone know a commercial product utilizing either
> homomorphic or structured encryption?
>
> Thank you in advance!
>

Structured encryption is a large and ambiguous topic, and I'm not sure
how many of the following are relevant to your intent.

Block chain applications use linked hashes to create append-only records.

Merkle Trees are a fairly common way to give someone a small 'hash'
value that enables them to verify whether some document is or is not
part of a very large archive, and also a way to make recursive queries
down the tree to find some
related values.  This is typical in a lot of file sharing applications.
The user gets the 'root' of a Merkle tree and can then make queries down
the branches to find the document they're interested in. 

File sharing applications also use structured hashing to identify file
chunks for retrieval purposes.

Bloom filters are small-ish objects that a database can make available
to people allowing them to determine locally (subject to a some degree
of probabilstic chance) whether the database has a particular object,
without any further interaction with the database after obtaining the
filter.  The good part of this is that the queries the user makes are
not transmitted and can't be eavesdropped.  Nobody can tell what the
user searches for.  The bad part of this is that they provide no privacy
to the database server.  If someone has a document hash, they can check
the bloom filter to see if the document is there - that includes both
ordinary users, and copyright trolls looking for people to sue.

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.

Password testing tools use Rainbow Tables to check thousands of
passwords with each query whenever they can find a password database
where the passwords are encrypted but not salted.  Rainbow Tables have
become less important since all serious software developers have learned
that salting passwords is absolutely necessary.  That said, a lot of
not-very-serious software developers are nevertheless entrusted with
building customer databases. So security tools that include a password
breaker based on Rainbow Tables still find some use.

Are these examples of the kind of 'structured encryption' you were
asking about, or did you intend something more specific?

Bear



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20220224/82ec1dc6/attachment.htm>