Explained from scratch: private information retrieval and homomorphic encryption

https://blintzbase.com/posts/pir-and-fhe-from-scratch/

by blintz • 4 years ago

151 22 4 years ago

blintz7• 4 years ago

Author here, happy to answer any questions! I know it’s a complicated topic, and I’m still trying to figure out how best to explain it.

Also, we’ve applied to YC for W23 to commercialize and expand this tech; wish us luck!

timobile• 4 years ago

Just want to thank you for doing this!

ElCheapo• 4 years ago

Do you think homomorphic encryption will be the next hot thing in security-related sectors of tech?

blintz7• 4 years ago

I think it will be if we're successful!

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.

MattPalmer1086• 4 years ago

Very nice technical explanation, thanks.

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...

blintz7• 4 years ago

Yeah, the challenge always seems to building privacy technologies that people are actually willing to pay for.

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).

thethirdone• 4 years ago

Not really related to the article, but ever since I learned that homomorphic encryption exists I wondered if it is possible to make a trustless internet poker game.

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?

mhluongo• 4 years ago

Look into secure multi-party computation and "mental poker". I believe a version of this is solved today, but don't know the trust assumptions off the top of my head.

onetimeusename• 4 years ago

How does verification of data encrypted this way work say by the party that made the query? Like what is to verify that the cipher text was not tampered with? Can this be done?

blintz7• 4 years ago

There's no single way to do this kind of verification. Different applications will have different 'roots of trust' for the authenticity of database data.

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).

fjfbsufhdvfy• 4 years ago

I'm confused, it seems like this will require processing the entire database for every request, which would be unusable in practice. Did I miss the trick?

blintz7• 4 years ago

It does - for databases of a reasonable size, this is okay. Roughly 1-50 GB databases are quite practical.

mikewarot• 4 years ago

If the server has all the data, and does the homomorphic math, couldn't it selectively change some of the data inbound to a second job with the same user inputs, (in the background) and compare outputs, eventually using a a binary search to figure out what data was selected?

1vuio0pswjnm7• 4 years ago

"A naive solution is to download and store the entirety of Wikipedia; then, all your queries can be local and the server never learns anything. Unfortunately, this takes a lot of bandwidth and storage (~10 GB), so it isn't very practical."

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.

faizshah• 4 years ago

Is there a library for homomorphic encryption that application devs can use? Is it practical to use this technology yet?

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

Explained from scratch: private information retrieval and homomorphic encryption

Related Stories