blintz

Great question! The ciphertexts will be different every time, just like in standard encryption; the scheme uses something very similar to a nonce.

We are trying to avoid the "ECB Penguin", of course: https://crypto.stackexchange.com/questions/14487/can-someone...

Interesting that the hardest AP exams for it seem to be the English ones. I wonder why?

A big part of this company has turned out to be figuring out how to explain FHE :)

I'm working on a higher-level "why/how to use this" blog post that should help. Thanks for the suggestions!

Love the idea of running this stuff on-prem / in house. Just not being beholden to random updates in the rules or logging policies seems like a big value add. +1 to the other commenter who mentioned they'd love to see a version for smaller teams - there might be more privacy-oriented teams out there than you'd expect. I think even a version that can run in public clouds would be meaningful.

Have you gotten feedback from folks using it on how it compares to Copilot in terms of usefulness? What's the 'order of magnitude' difference?

It's FHE applied to solve a variant of oblivious transfer, called "private information retrieval" (https://en.wikipedia.org/wiki/Private_information_retrieval). PIR is very similar to oblivious transfer, except that in oblivious transfer, the privacy is mutual - the client learns exactly one element from the database; in PIR, it's ok if the client learns some number of 'extra' items other than the one it queried.

It's 1-2 seconds for a 1 GB database with millions of items.

(A couple years ago this was more like minutes, and about 10 years ago it would have taken hours!)

Sure! End-to-end encryption (E2EE) in a messaging context is about the service provider (Meta for WhatsApp, Apple for iMessage) not learning the contents of messages sent on the platform. E2EE also gets used when referring to backups, where it again refers to the service provider of the backups not learning the contents of backups.

Private retrieval is a more general concept, which refers to retrieving data from a server without letting it learn your access pattern. In a specific application, it's easier to see the contrast: for example, in our password checker (https://playground.blyss.dev/passwords), the data that Blyss helps keep encrypted, and prevents the server from learning, is which password you are checking. With standard E2EE techniques, it would not really possible to keep your query private.

In messaging, Blyss can be used to build messaging services that not only do not learn what you say (the standard E2EE guarantee), but also do not learn who you talk to. We're working on this, but it's a tricky thing to ship.

We don't think this guarantee is only useful to bad actors, in the same way that end-to-end encryption has turned out to be useful even if you're not doing something illegal.

The businesses using Blyss want to perform tasks (like scanning for breached credentials) without seeing sensitive customer data. Even the US government's civilian cybersecurity agency, CISA, recommends that you use end-to-end encrypted solutions for credential vaults (https://www.cisa.gov/news-events/cybersecurity-advisories/aa... Blyss is an added layer for these services, protecting even access metadata.

Thanks! The secret client key stays in the browser or app. It's used to encrypt queries, and decrypt the server responses.

Yes, the server multiplies the query by the entire 8 GB every time. It’s not as slow as it sounds :-) … it’s basically limited by memory bandwidth.

Yeah, we do return the full row. It does leak the hashes, but these are already public (you can directly download them from the Have I Been Pwned website).

Under the hood, we don’t actually send the full hashes back; we can get away with just sending back fewer bits (enough to minimize the chance of a false positive).

Hey, I made this! Happy to answer any questions.

I wonder if there's a number class for the value that the sides take. Are they all ultimately numbers formed with standard operations and radicals? Or are there some that we have only found with like 'numeric' techniques?

I’m sure this article is right about some stuff, but man if it doesn’t make me sad to read.

Software can be so exciting and fun, and this “careerist” perspective really sucks the joy out of it.

If you’re looking for something that is kind of the opposite of this article: https://ferd.ca/the-little-printf.html.

FWIW, symmetric encryption like AES-256 GCM is just astoundingly unlikely to be “broken” in the next ~20 years (or perhaps ever…)

There’s more of a case for public-key stuff changing, but this doesn’t rely on anything public key.

Cool project! This stuff is all possible thanks to the SubtleCrypto API (https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypt...), which became widespread in browsers in the last ~5 years. It's so great we don't have to use weird libraries (some with pretty gnarly side channel leakage) to do cryptography anymore.

It wouldn't be that crazy for the browser to do the encryption part for me, right? Like, what if in the 'save this page' dialog my browser actually did the encryption, and then generated this 'self-decrypting page' for me if I checked a box saying "encrypt with password"? Would be a nice way for regular non-technical people to encrypt things and send them to each other.

We use standard hardware, with some special attention paid to making sure we maximally leverage AVX2/AVX512. The computation is naively parallel and very simple, so better hardware doesn't seem terribly likely to decrease costs. If anything would work, our bet is on GPU's, which seem to offer better memory bandwidth and are widely commercially available.

FHE for ML is indeed not super practical yet. There are some recent works that get quite close: CryptGPU (https://arxiv.org/pdf/2104.10949.pdf) and Piranha (https://www.usenix.org/system/files/sec22-watson.pdf) both leverage GPU's for private ML (and even some MPC!).

Yeah, there is a a bit of cold-start problem with respect to standards / certification. People kinda have to widely use something before it seems worthwhile to standards bodies to write standards, but often folks are sensibly cautious about using non-standardized cryptography. The solution is to get lots of eyeballs on it, get large organizations to really want to use it, and use that push to get standards rolling.

Personally, I think highly regulated fields like health care etc will adopt this technology extremely slowly. Academic cryptographers really like health care applications but, as you said, in practice, compliance is the main objective of health care organizations.

We are more interested in applications where privacy is actually a value add or a liability minimizer. For example, a VPN using our service could differentiate or charge more to users for offering a completely private DNS option. A crypto wallet could actually advertise (and perhaps even prefer!) that it doesn't spy on you.

Yeah, we think private lookup could make distributed retrieval protocols like IPFS, BitTorrent, etc significantly more private. Currently, they are in some ways much worse from a privacy perspective than centralized alternatives, since they involve broadcasting information about each retrieval to a large number of peers; the ability to do private lookups could really help fix this.

I think FHE is so powerful that we tend to let the cool possibilities distract from really practical and useful stuff that is possible today. Today, I think just the ability to do private lookups is, while super simple from an academic lens, could be really powerful. Plus, if it gets widely used, the underlying tech will mature, and then the more exotic stuff (multiple clients, more complex computations) becomes more realistic.

We're currently building a service that will let you do private lookups without needing to really mess with the underlying cryptography or schemes. You'll be able to use it to deliver even stronger privacy than E2EE ("E2EE+"?). For example, DNS that doesn't learn what you resolve (this is beyond something like DNS-over-HTTPS), or a messaging service that doesn't learn who you talk to.

As far as learning more, I wrote a blog post that tries to cover the basics of doing private lookups: https://blintzbase.com/posts/pir-and-fhe-from-scratch/.

Hey, creators here, cool to see people excited about this! We're in the YC W23 batch, happy to answer any questions folks have.

That’s a fair point, although you can use a debit card for cannabis delivery services too. Maybe a good mitigation for the fraud concern is just using ‘virtual’ or physical prepaid debit cards that have a fixed balance.

I guess I don’t quite understand why using something like a debit card doesn’t work. The marijuana companies seem to have effectively figured how to take payments with almost no help from the traditional players (credit card companies, banks).

Happy to answer any questions! Yeah, we're taking a narrow application (fetching from a database) and making it really practical. You can privately check a Bitcoin balance at https://btc.usespiral.com or privately read Wikipedia at https://spiralwiki.com. Our code for the Bitcoin site is at https://github.com/spiralprivacy/clients.

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

Yeah, I‘d agree that performance is the crux of the issue for many PETs.

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.

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

Yeah, a lot of cool folks are working on doing ML on encrypted data (Zama, Enveil, Duality). It's a really challenging problem, and I think it will take a big, well-funded team to get working well. We're partly interested in PIR because it's much more tractable, and we are able to make really significant progress on it as a scrappy two-man team.

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.

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

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.

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!