6 ms·

What kind of operations can one actually do on the encrypted data? I'm struggling to understand what the use cases are (I saw the one about machine learning, b

What kind of operations can one actually do on the encrypted data? I'm struggling to understand what the use cases are (I saw the one about machine learning, but thats broad and vague.)

faeyanpiraat 6y ago
Multiplication is certainly possible (thats why ML works with it)
daenz 6y ago
It has the potential to re-invent how we use compute services. A company can provide service X that is guaranteed to not be able to see the data you give it. Personally, I think it is the most applicable to the corporate "giants" of the world: now they can feel more free to offer each other services that operate on data that would normally be considered too risky to share, like financial data or private customer data. When the data is secured through FHE, there's no risk to letting anyone else run computations on it in order to provide you with value.
- mistrial9 6y ago
  sure, but think of this.. Most people will say that listening in to a phone conversation is 'spying' and not right, and, it turns out that listening is hard, due to poor connections, accents and other noisey issues. BUT at scale, simply collecting and mapping the patterns of connection/duration over time is much more informative than most people imagine, and few object to that. Surprise. Run the scenario you describe, and people being intrusive, rent-collecting bullies that they can be, and do you think the sole-sourcing of "giants" will be a tame and orderly affair ? There are two directions to take that thought at least.. one is, what did previous groups do in past times that did create positive results; and second, a tech games-theory approach to de-centralization mixed with special purpose business entities, with real checks and balances. Personally, I assume that business cannot be trusted over time to keep the consumer of services best result in mind.
llarsson 6y ago
The other thread we had about this stated that arbitrary math is possible, but slow as heck (40 times slower or so). You can either tell it to operate on two encrypted items ("multiply value 2 and 4 from the data") or give either operand as-is ("add 5 to value 3 in the data"). So general-purpose, apparently. Just slow.
- jstanley 6y ago
  Is it really only 40 times slower? I thought it was millions of times slower. If it's only 40 times slower than a modern CPU, then this technology is a lot more interesting than I thought. From a few minutes of Googling, I can't find any obvious benchmarks.
  - betterunix2 6y ago
    It depends on what you are computing. In some cases it will be as fast as the insecure version (not counting encryption/decryption time). On the other hand, random access will have to be simulated by a linear scan over an array, which is asymptotically slower. Complex control flow e.g. deeply nested loops with input-dependent side effects can cause the overhead to balloon.
  - onepointsixC 6y ago
    This article[1] has IBM slides which suggest 40-50x computation penalty and 10-20x RAM penalty. [1]: https://arstechnica.com/gadgets/2020/07/ibm-completes-successful-field-trials-on-fully-homomorphic-encryption/ https://arstechnica.com/gadgets/2020/07/ibm-completes-succes...
    - dowem 6y ago
      Thanks for passing on that reference @onepointsixC. Yourself and the parent poster might be interested in a webinar we posted on YouTube which talks about those slides from one of the paper authors (Flavio) and yours truly. That slide is about halfway through the video, but the whole thing is worth a watch. https://www.youtube.com/watch?v=W9G1s1t_d80&list=PL0VD16H1q5IOEQuRdgRVt1M8uQSbpVzTb&index=2 https://www.youtube.com/watch?v=W9G1s1t_d80&list=PL0VD16H1q5... We put up a cryptography playlist during the last week on youtube since it felt like people didn't have enough resources to refer to easily. We hope it helps! It includes the video walkthrough of how to get the toolkit running and run some demos.
Darkstryder 6y ago
To give an answer a bit more technical than the others, theoretically a encryption scheme is considered fully homomorphic if it can support an arbitrary number of additions and multiplications on its inputs (bits or integers). In a lot of fully homomorphic encryption (FHE) schemes bits are represented through big matrices that are in part random and part deterministic. You can add and multiply these matrices and it will naturally add and multiply the encrypted bit inside as well, but you need the secret key to decrypt the matrix and learn if it contains a one or a zero. From these operations (add and mul) you can create a NAND gate using the formula 1 - A * B (assuming A and B are matrices containing encrypted bits) and create any arbitrary boolean circuit from there. These circuits works on the encrypted data without the need to decrypt it. (there is an additional step called bootstrapping that most schemes require in order to allow circuits of unlimited depth but I won’t get into that in such a short answer)
- KaiserPro 6y ago
  Excellent, thank you! Seeing that one can NAND things, everything makes a lot more sense.
throw0101a 6y ago
Perhaps: > In this paper we present an electronic voting system based on homomorphic encryption to ensure privacy, confidentiality in the voting. Our proposal offers all the advantages of the multiplicatively homomorphic encryption cryptosystems. The proposed voting scheme is suitable for multi-candidate elections as well as for elections in which contains neutral votes. * https://ieeexplore.ieee.org/document/7492759 https://ieeexplore.ieee.org/document/7492759 Others: > * Securing Data Stored in the Cloud. Using homomorphic encryption, you can secure the data that you store in the cloud while also retaining the ability to calculate and search ciphered information that you can later decrypt without compromising the integrity of the data as a whole. > * Enabling Data Analytics in Regulated Industries. Homomorphic encryption allows data to be encrypted and outsourced to commercial cloud environments for research and data-sharing purposes while protecting user or patient data privacy. […] * https://www.venafi.com/blog/homomorphic-encryption-what-it-and-how-it-used https://www.venafi.com/blog/homomorphic-encryption-what-it-a... White paper from a Microsoft crypto conference: * http://homomorphicencryption.org/white_papers/applications_homomorphic_encryption_white_paper.pdf http://homomorphicencryption.org/white_papers/applications_h...
betterunix2 6y ago
In theory any decidable function (any function that is guaranteed to terminate on any input). You need the control flow to be independent of the inputs, otherwise it would not really be "encrypted" (input-dependent control flow would reveal something about the inputs), but it is always possible to transform a (decision) function into its "input oblivious" version without too much of a performance hit. In the case of FHE, the "instruction set" is just addition and multiplication i.e. the computation is expressed as a polynomial. Practicality is a problem. You cannot have random access without performing some kind of linear scan over an array (all of which is expressed as a polynomial), so most software will perform extremely poorly. The actual cryptosystems are reasonable in terms of performance, but still carry a significant overhead. Even for ML tasks you are probably looking at 100-1000x performance overhead.
- dogma1138 6y ago
  Can the performance overhead be latency masked down the line so you don’t have as much overhead in practice? For example compression of slow storage media like tapes technically adds overhead but in practice because the slowest part of the chain is usually reading/writing off the tape you either don’t experience any actual overhead in practice or even often experience a small speed increase unless you can massively parallelize media access with multiple heads at which point the CPU/RAM becomes the bottleneck again.
  - jlokier 6y ago
    It depends on the task. Some tasks intrinsically require a lot of random access to a large memory, meaning a memory larger than your fast CPU, and there is no way to buffer enough state inside the small memory of the CPU to make the random access non-random. (Note, random access here really means data-dependent addresses that don't follow patterns you can predict without doing the computation; they are not really random.) For those tasks, address traffic from the CPU to the memory reveals information even if the data is encrypted, and this is the reason why it is said to require a linear scan of memory to perform random access while hiding the address of interest. A more extreme version of this occurs with scanning large databases without revealing what you're looking for. I'm not sure if the full linear scan is really essential, or if there's a way of representing data in memory (or data store) differently that relaxes the full scan requirement. E.g. by having the memory itself do some polynomial processing.
SilasX 6y ago
Per the discussion from Friday[1], any function that you can unroll into a (stateless) circuit. Edit: which, AIUI, means any function where you can a) prove it halts, and b) recursion and loops are converted into loops that execute for a constant number of loops known at compile time. [1] https://news.ycombinator.com/item?id=24007566 https://news.ycombinator.com/item?id=24007566

What kind of operations can one actually do on the encrypted data? I'm struggling to understand what the use cases are (I saw the one about machine learning, but thats broad and vague.)

faeyanpiraat 6y ago

Multiplication is certainly possible (thats why ML works with it)

daenz 6y ago

It has the potential to re-invent how we use compute services. A company can provide service X that is guaranteed to not be able to see the data you give it. Personally, I think it is the most applicable to the corporate "giants" of the world: now they can feel more free to offer each other services that operate on data that would normally be considered too risky to share, like financial data or private customer data. When the data is secured through FHE, there's no risk to letting anyone else run computations on it in order to provide you with value.

mistrial9 6y ago
sure, but think of this.. Most people will say that listening in to a phone conversation is 'spying' and not right, and, it turns out that listening is hard, due to poor connections, accents and other noisey issues. BUT at scale, simply collecting and mapping the patterns of connection/duration over time is much more informative than most people imagine, and few object to that. Surprise. Run the scenario you describe, and people being intrusive, rent-collecting bullies that they can be, and do you think the sole-sourcing of "giants" will be a tame and orderly affair ? There are two directions to take that thought at least.. one is, what did previous groups do in past times that did create positive results; and second, a tech games-theory approach to de-centralization mixed with special purpose business entities, with real checks and balances. Personally, I assume that business cannot be trusted over time to keep the consumer of services best result in mind.

llarsson 6y ago

The other thread we had about this stated that arbitrary math is possible, but slow as heck (40 times slower or so). You can either tell it to operate on two encrypted items ("multiply value 2 and 4 from the data") or give either operand as-is ("add 5 to value 3 in the data"). So general-purpose, apparently. Just slow.

jstanley 6y ago
Is it really only 40 times slower? I thought it was millions of times slower. If it's only 40 times slower than a modern CPU, then this technology is a lot more interesting than I thought. From a few minutes of Googling, I can't find any obvious benchmarks.
- betterunix2 6y ago
  It depends on what you are computing. In some cases it will be as fast as the insecure version (not counting encryption/decryption time). On the other hand, random access will have to be simulated by a linear scan over an array, which is asymptotically slower. Complex control flow e.g. deeply nested loops with input-dependent side effects can cause the overhead to balloon.
- onepointsixC 6y ago
  This article[1] has IBM slides which suggest 40-50x computation penalty and 10-20x RAM penalty. [1]: https://arstechnica.com/gadgets/2020/07/ibm-completes-successful-field-trials-on-fully-homomorphic-encryption/ https://arstechnica.com/gadgets/2020/07/ibm-completes-succes...
  - dowem 6y ago
    Thanks for passing on that reference @onepointsixC. Yourself and the parent poster might be interested in a webinar we posted on YouTube which talks about those slides from one of the paper authors (Flavio) and yours truly. That slide is about halfway through the video, but the whole thing is worth a watch. https://www.youtube.com/watch?v=W9G1s1t_d80&list=PL0VD16H1q5IOEQuRdgRVt1M8uQSbpVzTb&index=2 https://www.youtube.com/watch?v=W9G1s1t_d80&list=PL0VD16H1q5... We put up a cryptography playlist during the last week on youtube since it felt like people didn't have enough resources to refer to easily. We hope it helps! It includes the video walkthrough of how to get the toolkit running and run some demos.

Darkstryder 6y ago

To give an answer a bit more technical than the others, theoretically a encryption scheme is considered fully homomorphic if it can support an arbitrary number of additions and multiplications on its inputs (bits or integers). In a lot of fully homomorphic encryption (FHE) schemes bits are represented through big matrices that are in part random and part deterministic. You can add and multiply these matrices and it will naturally add and multiply the encrypted bit inside as well, but you need the secret key to decrypt the matrix and learn if it contains a one or a zero. From these operations (add and mul) you can create a NAND gate using the formula 1 - A * B (assuming A and B are matrices containing encrypted bits) and create any arbitrary boolean circuit from there. These circuits works on the encrypted data without the need to decrypt it. (there is an additional step called bootstrapping that most schemes require in order to allow circuits of unlimited depth but I won’t get into that in such a short answer)

KaiserPro 6y ago
Excellent, thank you! Seeing that one can NAND things, everything makes a lot more sense.

throw0101a 6y ago

Perhaps: > In this paper we present an electronic voting system based on homomorphic encryption to ensure privacy, confidentiality in the voting. Our proposal offers all the advantages of the multiplicatively homomorphic encryption cryptosystems. The proposed voting scheme is suitable for multi-candidate elections as well as for elections in which contains neutral votes. * https://ieeexplore.ieee.org/document/7492759 https://ieeexplore.ieee.org/document/7492759 Others: > * Securing Data Stored in the Cloud. Using homomorphic encryption, you can secure the data that you store in the cloud while also retaining the ability to calculate and search ciphered information that you can later decrypt without compromising the integrity of the data as a whole. > * Enabling Data Analytics in Regulated Industries. Homomorphic encryption allows data to be encrypted and outsourced to commercial cloud environments for research and data-sharing purposes while protecting user or patient data privacy. […] * https://www.venafi.com/blog/homomorphic-encryption-what-it-and-how-it-used https://www.venafi.com/blog/homomorphic-encryption-what-it-a... White paper from a Microsoft crypto conference: * http://homomorphicencryption.org/white_papers/applications_homomorphic_encryption_white_paper.pdf http://homomorphicencryption.org/white_papers/applications_h...

betterunix2 6y ago

In theory any decidable function (any function that is guaranteed to terminate on any input). You need the control flow to be independent of the inputs, otherwise it would not really be "encrypted" (input-dependent control flow would reveal something about the inputs), but it is always possible to transform a (decision) function into its "input oblivious" version without too much of a performance hit. In the case of FHE, the "instruction set" is just addition and multiplication i.e. the computation is expressed as a polynomial. Practicality is a problem. You cannot have random access without performing some kind of linear scan over an array (all of which is expressed as a polynomial), so most software will perform extremely poorly. The actual cryptosystems are reasonable in terms of performance, but still carry a significant overhead. Even for ML tasks you are probably looking at 100-1000x performance overhead.

dogma1138 6y ago
Can the performance overhead be latency masked down the line so you don’t have as much overhead in practice? For example compression of slow storage media like tapes technically adds overhead but in practice because the slowest part of the chain is usually reading/writing off the tape you either don’t experience any actual overhead in practice or even often experience a small speed increase unless you can massively parallelize media access with multiple heads at which point the CPU/RAM becomes the bottleneck again.
- jlokier 6y ago
  It depends on the task. Some tasks intrinsically require a lot of random access to a large memory, meaning a memory larger than your fast CPU, and there is no way to buffer enough state inside the small memory of the CPU to make the random access non-random. (Note, random access here really means data-dependent addresses that don't follow patterns you can predict without doing the computation; they are not really random.) For those tasks, address traffic from the CPU to the memory reveals information even if the data is encrypted, and this is the reason why it is said to require a linear scan of memory to perform random access while hiding the address of interest. A more extreme version of this occurs with scanning large databases without revealing what you're looking for. I'm not sure if the full linear scan is really essential, or if there's a way of representing data in memory (or data store) differently that relaxes the full scan requirement. E.g. by having the memory itself do some polynomial processing.

SilasX 6y ago

Per the discussion from Friday[1], any function that you can unroll into a (stateless) circuit. Edit: which, AIUI, means any function where you can a) prove it halts, and b) recursion and loops are converted into loops that execute for a constant number of loops known at compile time. [1] https://news.ycombinator.com/item?id=24007566 https://news.ycombinator.com/item?id=24007566