It's an exciting time to be working in homomorphic encryption!
Having third parties compute on encrypted, private data, and return results without being able to know the inputs or outputs is pretty amazing.
Trying to understand where this would come in handy.
But something like "analyze this list of customer records for fraud" or "analyze this proprietary data for trends" has previously either required a lot of trust that your cloud provider isn't going to siphon your data, or just required on-prem hardware that you cannot scale as easily.
If "math on encrypted data" works, we could keep our data confidential while still sending of batches of it to be number-crunched at a cloud provider.
Or even start talking about distributed / peer-to-peer computing, where a swarm of users (or, say, businesses that wish to cooperate) can send compute jobs to each other without having to trust that the other members weren't going to go snooping through the data that was sent.
How is that even possible? That seems to defeat the purpose of encryption, or at least show that our encryption is severely flawed.
This is the first time I've heard of this and it's kind of blowing my mind
It seems to me that this intrinsically is vulnerable to side-channel attacks, but it will be interesting to see if we can avoid those with constant-time algorithms or something.
This isn’t really a particularly well-informed suspicion: it’s partly based on a sense that FHE is a “have your cake and eat it too” sort of technology that’s too good to be true and partly based on the recent discoveries that fairly well-understood things like speculative execution in CPUswere vulnerable to serious side-channel attacks.
However, that effectively means that any FHE approach has to be "anti-optimized", always touching all the data that might get touched, always taking all the conditional paths, not just the worst case path as in constant time algorithms, since the execution must return the correct result for any encrypted input data.
It's not that you can "see if we can avoid those with constant-time algorithms or something", the basic table stakes (which all FHE methods actually implement) is the constant-time algorithm approach taken to the extreme and then squared.
It does have "some" unavoidable performance impact because of that.
Then the customer decrypts f(ab). This doesn’t imply any weakness in encryption.
FHE is a bit stronger than what I’ve described, but that’s the idea.
https://en.wikipedia.org/wiki/Paillier_cryptosystem
https://gist.github.com/noman-land/a65520aa4f2ce7ba3bf9f13d2...
Like, for a true need you could imagine someone saying "I really want this, no matter how it costs" - but you wouldn't do that for elastic compute if doing that locally was 100x cheaper; and in a similar way, the "wish to cooperate" by sending compute jobs to each other is meaningful if and only if you can actually save effort this way, but if there's a 100x overhead cost for FHE (and in reality it's far worse than mere 100x), that doesn't make sense, and you'd simply be better off doing it without distributed / peer-to-peer / cloud computing and just buy and maintain your own non-shared hardware even if it's used only 5% of the time.
And I'm not sure if FHE can ever get to overhead rates so low that these use cases would start to make sense, like, there's no good reason to assume that a mere 10x overhead FHE is even theoretically possible.
One paper I used showed how X-rays can be analyzed without exposing the X-ray data itself.
This can be generalized more to any situation where one party owns a proprietary algorithm and another party owns sensitive input data but they don't trust each other.
Modern LLMs are actually the perfect example. You want to use chatgpt but they don't want to give you their model and you don't want them to see your input. If HME was more efficient, you could use it so that the person executing the model never sees your real input.
Is there any hope of getting the performance to the point where something like that would be feasible? I’d imagine the raw data itself would be so big that the performance for anything non trivial would be unworkable.
In practice, I don’t think those costs are that high because the rate of incident is low and the average damage is also low.
Yes there are outlier instances of large breaches but these seem like high profile aircraft crashes considering how many entities have sensitive data.
And then there's the example of businesses that work with lots of confidential customer data, like banks or doctors. Again, you can sue your vendor for breach of contract if they behave irresponsibly with your data, but your customers may not care; you're going to suffer a hit to your reputation regardless of whether or not the breach was your fault.
I guess the better comparison is that cost in a financial statement plus some expected increase in revenue due to a “better” product.
Again, I think you are correct in your analysis of the improvements but that contributes little to the revenue as explaining the benefit to most customers requires framing your existing product as potentially harmful to them. Educating them will be hard and it may result in an offsetting realization that they were unsafe before and as a result were paying too much.
Yes the C-Suite is thinking about and mitigating risk. They probably know the exact number for a given class of risk in terms of current mitigation costs. You have to beat that by a margin wide enough for them to take action.
Even if you know their numbers and know you beat it by enough to warrant the deployment you will still get bumped if someone sells them a path to increasing revenue.
The out I gave was to frame it as value added (more revenue) and that is where you risk devaluing your current product.
If you frame it as cost reduction you are capped in both price and interest by the current, necessarily acceptable, levels of risk and cost of mitigations.
We should consider what kinds of computational tasks today’s responsible parties (or their regulators, or their insurers) think of as too risky to casually trust to third parties under the status quo. For example with my block storage provably unintelligible if you don’t have the HSM I keep safely in my corporate dungeon, I’m comfortable not caring whose racks the encrypted blocks sit on. I’d have to vet those vendors a lot harder if they could read all my super secret diaries or whatever.
And, for that matter, it’s on the service provider side too, right? Even the contractual, spit-and-handshake pinky-swear-based mode of enforcement comes with significant compliance costs for service providers, especially ones operating in regulated industries. Perhaps it’s not too much to hope that effective and efficient HME techniques might reduce those service providers’ compliance costs, and lower the barrier to entry for new competitors.
I’m reminded how even non-tech people in my life became much more willing to trust their credit card details to online retailers once they felt like a little green lock icon made it “safe”. Of course a LOT changed over that same period, but still: the underlying contractual boundaries didn’t substantially change—in the US the customer, then as now, has only ever been responsible for a certain amount of fraud/theft loss—but people’s risk attitudes updated when the security context changed, and it opened up vast new efficiencies and lines of business.
Reduction of trust is not a value add, it is a cost reduction. Maybe that cost is blocking a valuable product/service but either that product/service’s value is less than the current cost of trust OR trust has to be far more costly in the context of the new product/service.
It’s only the latter that I find interesting which is why tend to be pretty hard on suggestions that this will do much for anything that currently exists. At best, it will improve profits marginally for those incumbents.
What is something where the price of trust is so catastrophically high in modern society AND HME can reduce that cost by orders of magnitude? Let’s talk about that rather than HME.
The hard parts here are retrofitting society to use a digital ID and how to prove that the human in front of you is attached to that digital ID.
The solutions there all seem like dystopias where now instead of a bouncer looking at your ID for a few seconds, technology is taking pictures of you everywhere and can log that with location and time trivially.
Age depends on timestamp. The encrypted data is stored on the ID and signed by the DMV, with a function that can be run by the bouncer's scanning machine that plugs in a now() timestamp, and receives a boolean in return. The DMV doesn't even need to be involved after the issuance of the ID and no network access is needed for this calculation.
No one's location was tracked and no one's picture was taken and now a bouncer who fancies you can't turn up at your house after glancing at your ID.
There’s lots of other ways to solve the problem for verification/signing use cases tbh. Homomorphic encryption shines best when you are looking at more complex calculations than just a Boolean result - such as tax calculations.
Can you submit your financial information and have your taxes calculated without revealing the amounts involved? Can you apply filters to an image without having the image readable by the server? It essentially allows us to “trust a remote server” in scenarios where one wouldn’t usually.
The whole value prop is built on not trusting that bouncer and by extension their hardware.
Everything would have to be encrypted leading to the bouncer also needing to establish that this opaque identifier actually belongs to you. This is where some picture or biometric comes into play and since the bouncer cannot evaluate it with their own wetware you are surrendering more data to a device you cannot trust.
They also cannot trust your device. So, I don’t see a scenario where you can prove ownership of the ID to a person without their device convincing them of it.
I assume you mean the bouncer didn't take a photo, they just looked at the DMV photo embedded in the ID and did a visual comparison in their meat brain.
If there's no photo anywhere, how does the bouncer know I'm not using someone else's ID?
https://news.ycombinator.com/item?id=37981190 :
> How can they be sure what's using their CPU?
Firefox, Chrome: <Shift>+<Escape> to open about:processes
Chromebook: <Search>+<Escape> to open Task Manager
Concretely (and simplistically) - I give you two numbers, 2 & 2, but they're encrypted so you don't know what they are, and you add them together for me, but that's also encrypted so you don't even know that the sum of the inputs I gave was 4. It's 'computation on encrypted data', basically.
That now generalizes to any computation (not just addition), because there is a logically complete set of primitive operations for which fully homomorphic encryption (FHE) can be done.
Caveats:
1) You can't actually do e.g. while loops with run time unknown. All such FHE computations are done by generating a fixed size boolean circuit for a given input size. It's "Turing-complete" in the sense that you can size up the circuit to any input size, but it wouldn't directly implement an unbounded while loop -- you have to generate a different "program" (circuit) for each input size.
2) All such computations must have a fixed output size -- else it leaks information about the data inside. So allowable computations would be like, "give me the first 30 bytes of the result of querying for names in the set that begin with A". If there are no results, the output still has to be 30 bytes.
3) For similar reasons, any FHE computation must look at all bits of the input (otherwise, it leaks info about what's in them). "See if this value is in the set" can't just jump to the relevant section.
4) The untrusted third party knows what computation you're doing (at least at a low level), just not the data it's being performed on or the result.
5) As you might have expected from 3), there's a massive blowup in resources to do it. There can be improvements, but some blowups are inherent to FHE.
and image processing with FHE is really not a stretch of the imagination. https://github.com/microsoft/EVA/blob/main/examples/image_pr...