Explained from scratch: private information retrieval and homomorphic encryption
blintzbase.com
blintzbase.com
Also, we’ve applied to YC for W23 to commercialize and expand this tech; wish us luck!
That would entail some type of homomorphic encryption where each party would get to know which cards they drew, but not anyone elses. The type of system I am imagining has each player generate a permutation of 52 cards, encrypt it with their key and then take everyone's encrypted permutations together and decrypt a result where they only get to see the 5 cards they got dealt.
Is there any research into multi-key systems or ways to apply a single key system to get the kind of result I am looking for?
The technology is cool, but I wonder what kind of market you think might exist for it?
Some years back I worked for a privacy startup, but we never really figured that out...
The one trove of public data that folks seem really eager to access in a metadata-private way seems to be blockchain data. As someone who was not really a blockchain person, I've been really pleasantly surprised by how much interest people in that field take in our tech. In the short run, we are definitely focused on this area.
I do think there are significant applications beyond that though: I am really personally excited by metadata-private messaging/email and sensitive datasets (financial data, medicine/health data, cybersecurity data).
I think the killer application for homomorphic encryption (HE) will be on the regulated and sensitive data as you have mentioned. In healthcare, high accuracy machine learning requires massive datasets and it is difficult to get your hands on the data mainly due to privacy concerns. If HE can make data available to be analyzed without compromising the patients' anonymity it will be a game changer and perhaps can relax on the accessibility of the sensitive clinical data in the near future.
Just wondering, can we not achieve similar privacy using secret sharing (SS) cryptography for anonymity? With (SS) unlike HE, you can perform arbitrary calculations in the encrypted domain [2].
[1]How to Share a Secret:
https://news.ycombinator.com/item?id=31817716
[2]Secure multi-party computation:
https://en.m.wikipedia.org/wiki/Secure_multi-party_computati...
Multi-party computation is also a cool piece of technology. I think that I was always drawn to HE because it involves a completely trustless relationship with the server; in MPC, there's more a of a "m/n parties don't collude" assumption, that can be tricky to implement in practice. (Also side note: you can in theory perform arbitrary computation on encrypted data using FHE; the performance impact is really significant, like 100-10000x, but you can perform unlimited computation).
Surprisingly, these two concepts (MPC and HE) work quite well when combined! There are some computations each is suited to computing efficiently (linear for HE, non-linear for MPC), so when combined for ML, you get really good results. See this landmark paper and the follow on work: https://eprint.iacr.org/2018/073.pdf.
FHE is painfully slow. The only real domains it can work realistically are for very simple computations. You are putting the cart miles ahead of the donkey here.
For example, for Wikipedia, we could imagine the Wikipedia site serving the PIR themselves (they are already the entity you trust to decide what is on Wikipedia). A third party wishing to mirror Wikipedia over PIR might try to get some kind of digital signature over the contents of each article from Wikipedia or another trusted source.
For blockchain queries, there are more technical solutions. For Bitcoin, for example, we could include a Merkle tree proof-of-inclusion for the transaction (a la BIP 37).
I do think the cool thing about what we're building is you don't really have to understand exactly what homomorphic encryption is to use / benefit from it.
We're really just building a database that can't learn what rows you read, which is useful (and practical!) across a bunch of domains. The fact that it uses homomorphic encryption under the hood is cool, but hopefully you don't need to get too bogged down in the details to use it.
I am not terribly confident that over the next 5 years we will see anything like a 10x or 100x improvement in general fully homomorphic encryption.
Instead, I think we already have some domains for which FHE is really practical today (like private information retrieval), and we should focus on those. In these domains, the cost overhead of PIR is less than ~10-100x, and negligible for many real-world scenarios.
We can pretend this is a large amount of data but that notion becomes less believable each year, as bandwidth and storage capacity keep increasing.
Many of us now stream (=download and throw away) much more than 10GB on a regular basis.
Local databases, where queries never leave the computer or the local network, exclude much of the "tech" industry that survives on monitoring and manipulating computer users through the internet. One would expect strong opposition from "tech" enthusiasts to any suggestion that a computer user can perform work or recreation offline.
"Tech" companies may not be the only ones. There is also that pathetic term "go dark" which hints at more surveillance being done through the internet.
If the computer user disconnects, it leaves many parties high and dry. Spending more time offline might not be a bad thing.
Edit: I found this library from Microsoft but it only supports addition and multiplication, not comparisons and sorting so it seems it’s not practical yet: https://github.com/microsoft/SEAL#microsoft-seal-1