7 ms·

Can you give an example of a useful computation someone would do against encrypted data? Trying to understand where this would come in handy.

daveguy 3y ago
It would come in handy with not requiring any trust of the cloud that is running your servers. For protected health information this could potentially be a major breakthrough in patient privacy.
hedora 3y ago
100% of the things you use Google for (drive, docs, search, personalization, maps, etc).
- fidotron 3y ago
  In an extreme case could Google use a mechanism like this to deny themselves direct access to the data they collect while still bidding in ad auctions based on that information?
janandonly 3y ago
Proving you have enough money without divulging the exact amount ?
- matheusmoreira 3y ago
  Wouldn't that be vulnerable to binary search? Like a guessing game?
NortySpock 3y ago
The general concept is "I want to keep this data private and confidential, but I want to be able to rent elastic compute for it". Previously, at the end of the day, the processor could only do useful work on unencrypted data. 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.
- alwa 3y ago
  And for that matter if I were a provider of some kind of computational service for hire, I (and my insurers) might feel a great deal of relief at the idea that we’re no longer having to sit on a big attractive ransomable pile of our clients’ data.
  - Out_of_Characte 3y ago
    Denial of service is still by far the most common tactic, encrypt the data and no one can use it.
- Obscurity4340 3y ago
  Has any world government implemented this in a similar/relevant fashion that illustrates this in action?
  - fragmede 3y ago
    No because this is the very bleeding edge of technology so there are only very limited (but very cool) tech demos of the technology? Nothing at scale yet. https://spiralwiki.com/ https://spiralwiki.com/
- calamari4065 3y ago
  Wait, so they're doing computation on encrypted data and inferring some information about the relationships between data in the encrypted set? 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
  - fiddlerwoaroof 3y ago
    The idea is the result is encrypted too such that, when the person that holds the key gets it back they can decrypt it and see the result. So you can run an inference algorithm on data without ever having to decrypt it and see what the data actually is. 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.
trompetenaccoun 3y ago
In addition to the other answers, any situation where you want to prove identity but want to preserve privacy at the same time. For example you could prove you're an adult citizen with ID without revealing your ID number, picture, or any private information whatsoever.
azeemba 3y ago
I had written an intro level blog post exploring image analysis use HME: https://azeemba.com/posts/homomorphic-encryption-with-images.html https://azeemba.com/posts/homomorphic-encryption-with-images... 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.
- koolba 3y ago
  > One paper I used showed how X-rays can be analyzed without exposing the X-ray data itself. 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.
- wanderingbort 3y ago
  If it’s just that the parties don’t trust each other then the cost of HME has to be compared to the current “state of the art” which is contracts and enforcement thereof. 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.
  - brendoelfrendo 3y ago
    Data incidents cause more problems than can easily be resolved with a contract lawsuit. Perhaps the data was siphoned by a 3rd party that hacked your vendor, or a malicious insider at your vendor sold it to a competitor. Sure, you can recoup some losses by suing your vendor for breach of contract, but once the data is leaked, it's never secret again. 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.
noman-land 3y ago
There are a few that I've thought about but the first one that comes to mind is proving you're 21+ to an alcohol store cashier without handing over your ID with all your personal info. You could just give them a ZK proof that returns a true/false and they could check it against encrypted data (signed by the DMV).
- wanderingbort 3y ago
  Why is that preferable over a message attesting “over 21” signed by the DMV? 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.
  - noman-land 3y ago
    It doesn't have to be a digital ID, it can just be encrypted data encoded on a regular ID on a QR code. 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.
    - captn3m0 3y ago
      Age verification (without leaking other PII) was the illustrative scenario for W3C Verified Credentials (it lets you use a validating authority to sign specific subset of your schema). 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.
dimastopel 3y ago
Imagine a search engine that gives you results without knowing your search query.
- jkhdigital 3y ago
  It would be hideously expensive due to the compute required and the total inability to monetize the data. Some people value their privacy that much; most don’t.
westurner 3y ago
Grading students' notebooks on their own computers without giving the answers away. https://news.ycombinator.com/item?id=37981190 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
OJFord 3y ago
All sorts - anything where you today give your data to some SaaS (and they encrypt it at rest, sure), and they then provide you some insight based on it or allow you to do something with it (by decrypting it, crunching numbers, spitting out the answer, and then encrypting the source data again) could potentially be done without the decryption (or the keys to make it possible). 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.
deleted 3y ago
[deleted]
SilasX 3y ago
It lets you have someone add up your numbers, and give you the sum, without knowing the input numbers or their sum. Basically, any time you want someone else to host the data, while you can also do queries/computations on it. 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.
podnami 3y ago
There are examples in cryptocurrency, where ZK proofs are all the rage. One use case is validating ownership of some amount of currency without knowing the actual amount, or verifying that a smart contract was executed correctly without revealing the specifics of the contracts internal state. Some blockchains use this in production, such as Polygons ZkEvm.
deleted 3y ago
[deleted]
spyder 3y ago
For example the Numerai hedge fund's data science tournament for crowdsourced stock market prediction is giving out their expensive hedge fund quality data to their users but it's transformed enough that the users don't actually know what the data is, yet the machine learning models are still working on it. To my knowledge it's not homomorphic encryption because that would be still too computational expensive, but it would be an ideal application for this. https://numer.ai/ https://numer.ai/
- jkhdigital 3y ago
  Whatever Numerai has done to their data, there is no indication that they actually transformed it in a way that would hold up to a theoretical cryptographic adversary.
rpearl 3y ago
Dropbox could generate photo thumbnails on encrypted photographs without ever looking at their contents, for example
- trompetenaccoun 3y ago
  No, that's not how it works.
  - rpearl 3y ago
    no, FHE should support arbitrary computation. and image processing with FHE is really not a stretch of the imagination. https://github.com/microsoft/EVA/blob/main/examples/image_processing.py https://github.com/microsoft/EVA/blob/main/examples/image_pr...

daveguy 3y ago

It would come in handy with not requiring any trust of the cloud that is running your servers. For protected health information this could potentially be a major breakthrough in patient privacy.

hedora 3y ago

100% of the things you use Google for (drive, docs, search, personalization, maps, etc).

fidotron 3y ago
In an extreme case could Google use a mechanism like this to deny themselves direct access to the data they collect while still bidding in ad auctions based on that information?

janandonly 3y ago

Proving you have enough money without divulging the exact amount ?

matheusmoreira 3y ago
Wouldn't that be vulnerable to binary search? Like a guessing game?

NortySpock 3y ago

The general concept is "I want to keep this data private and confidential, but I want to be able to rent elastic compute for it". Previously, at the end of the day, the processor could only do useful work on unencrypted data. 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.

alwa 3y ago
And for that matter if I were a provider of some kind of computational service for hire, I (and my insurers) might feel a great deal of relief at the idea that we’re no longer having to sit on a big attractive ransomable pile of our clients’ data.
- Out_of_Characte 3y ago
  Denial of service is still by far the most common tactic, encrypt the data and no one can use it.
Obscurity4340 3y ago
Has any world government implemented this in a similar/relevant fashion that illustrates this in action?
- fragmede 3y ago
  No because this is the very bleeding edge of technology so there are only very limited (but very cool) tech demos of the technology? Nothing at scale yet. https://spiralwiki.com/ https://spiralwiki.com/
calamari4065 3y ago
Wait, so they're doing computation on encrypted data and inferring some information about the relationships between data in the encrypted set? 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
- fiddlerwoaroof 3y ago
  The idea is the result is encrypted too such that, when the person that holds the key gets it back they can decrypt it and see the result. So you can run an inference algorithm on data without ever having to decrypt it and see what the data actually is. 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.

trompetenaccoun 3y ago

In addition to the other answers, any situation where you want to prove identity but want to preserve privacy at the same time. For example you could prove you're an adult citizen with ID without revealing your ID number, picture, or any private information whatsoever.

azeemba 3y ago

I had written an intro level blog post exploring image analysis use HME: https://azeemba.com/posts/homomorphic-encryption-with-images.html https://azeemba.com/posts/homomorphic-encryption-with-images... 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.

koolba 3y ago
> One paper I used showed how X-rays can be analyzed without exposing the X-ray data itself. 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.
wanderingbort 3y ago
If it’s just that the parties don’t trust each other then the cost of HME has to be compared to the current “state of the art” which is contracts and enforcement thereof. 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.
- brendoelfrendo 3y ago
  Data incidents cause more problems than can easily be resolved with a contract lawsuit. Perhaps the data was siphoned by a 3rd party that hacked your vendor, or a malicious insider at your vendor sold it to a competitor. Sure, you can recoup some losses by suing your vendor for breach of contract, but once the data is leaked, it's never secret again. 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.

noman-land 3y ago

There are a few that I've thought about but the first one that comes to mind is proving you're 21+ to an alcohol store cashier without handing over your ID with all your personal info. You could just give them a ZK proof that returns a true/false and they could check it against encrypted data (signed by the DMV).

wanderingbort 3y ago
Why is that preferable over a message attesting “over 21” signed by the DMV? 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.
- noman-land 3y ago
  It doesn't have to be a digital ID, it can just be encrypted data encoded on a regular ID on a QR code. 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.
  - captn3m0 3y ago
    Age verification (without leaking other PII) was the illustrative scenario for W3C Verified Credentials (it lets you use a validating authority to sign specific subset of your schema). 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.

dimastopel 3y ago

Imagine a search engine that gives you results without knowing your search query.

jkhdigital 3y ago
It would be hideously expensive due to the compute required and the total inability to monetize the data. Some people value their privacy that much; most don’t.

westurner 3y ago

Grading students' notebooks on their own computers without giving the answers away. https://news.ycombinator.com/item?id=37981190 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

OJFord 3y ago

All sorts - anything where you today give your data to some SaaS (and they encrypt it at rest, sure), and they then provide you some insight based on it or allow you to do something with it (by decrypting it, crunching numbers, spitting out the answer, and then encrypting the source data again) could potentially be done without the decryption (or the keys to make it possible). 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.

deleted 3y ago

[deleted]

SilasX 3y ago

It lets you have someone add up your numbers, and give you the sum, without knowing the input numbers or their sum. Basically, any time you want someone else to host the data, while you can also do queries/computations on it. 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.

podnami 3y ago

There are examples in cryptocurrency, where ZK proofs are all the rage. One use case is validating ownership of some amount of currency without knowing the actual amount, or verifying that a smart contract was executed correctly without revealing the specifics of the contracts internal state. Some blockchains use this in production, such as Polygons ZkEvm.

deleted 3y ago

[deleted]

spyder 3y ago

For example the Numerai hedge fund's data science tournament for crowdsourced stock market prediction is giving out their expensive hedge fund quality data to their users but it's transformed enough that the users don't actually know what the data is, yet the machine learning models are still working on it. To my knowledge it's not homomorphic encryption because that would be still too computational expensive, but it would be an ideal application for this. https://numer.ai/ https://numer.ai/

jkhdigital 3y ago
Whatever Numerai has done to their data, there is no indication that they actually transformed it in a way that would hold up to a theoretical cryptographic adversary.

rpearl 3y ago

Dropbox could generate photo thumbnails on encrypted photographs without ever looking at their contents, for example

trompetenaccoun 3y ago
No, that's not how it works.
- rpearl 3y ago
  no, FHE should support arbitrary computation. and image processing with FHE is really not a stretch of the imagination. https://github.com/microsoft/EVA/blob/main/examples/image_processing.py https://github.com/microsoft/EVA/blob/main/examples/image_pr...