5 ms·

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, otherw

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.
  - dowem 6y ago
    Thanks for helping the conversation along jlokier! I thought since you mentioned the database concepts in your response you might be interested in checking the database example in our toolkit. It is really not a literal database but rather an in-memory key value search as that is easier to code and demonstrate. One of the nuances of FHE programming is that a full table scan is needed for cases like our database search because fundamentally we cant test and branch to bail out early when we find something we want. Key comparison to an encrypted search key are obviously not literal matches. Each has its own polynomial representation with its own error added to keep terms from encrypting to the same value every time. There is no way to compare for short circuit evaluation for instance. So we end up doing an operation on each value and effectively summing up those partial solutions in a way that lets us determine if a match was found. If anyone is interested let us know on our public slack channel and someone can answer more tech details there. You guys rock. Great questions and comments on this forum.
    - jlokier 6y ago
      Thanks for the enthusiasm and insights - and the toolkit of course! :-) > fundamentally we cant test and branch to bail out early when we find something we want I think this is derived from assumptions that are not necessarily valid, with a suitable representation in memory. In other words I think you can bail early without revealing too much, with a suitable data encoding. But after writing out a sketch of a mechanism in a HN comment I realised the idea may be patentable, and HME is probably an attractor for that sort of thing. (I also realise I may be full of nonsense, but you've got to start somewhere :-) I'm pretty open about ideas. An open source kind of person. But then I remembered, I posted something before and found someone else built on the idea and patented it (citing my post), stopping me from developing the idea. Yes, that happened, albeit a long time ago :-/ Hmm, uncomfortable.
      - betterunix2 6y ago
        "In other words I think you can bail early without revealing too much, with a suitable data encoding." Maybe, but whatever that is would not be encryption. An FHE scheme is still a public key encryption scheme, so it should not be possible to compute any predicate over the message without having access to the private key. The homomorphic property allows you to compute a new ciphertext that will decrypt to the result of a computation, but that new ciphertext will still completely hide the plaintext. Basically the reason you cannot "bail out early" is that FHE does not allow you to see an indicator value to tell you when to do so -- any such value would itself be encrypted. If it were not, then it would reveal "something" about the inputs; coupled with the fact that the inputs can always be modified (by e.g. changing the function that is being computed), that would be a complete break. The only good technique we have right now for addressing this problem is to use some kind of interaction between multiple parties, which allows sublinear random access and can allow branching (and thus early loop terminations etc.). There are cases where that works well and there are many real-world use-cases of those techniques (I work on this for a large tech company). The tradeoff is that you need to do a lot of communication, which is typically more expensive than computation, and if too many parties are offline the computation will not proceed (in the two party case nobody can be offline). You also need to trust the parties not to collude with each other, which is sometimes a concern in practice.
- dowem 6y ago
  (Reminder I am a maintainer of the toolkit and an IBMer, opinions are my own, etc. ) This is a pretty new field with people just starting to take it seriously for large problems. It seems from what I have seen in experiments, there can be big tradeoffs in latency against throughput and like most software, decomposing the problem and efficiently mapping it onto the underlying data structures gets the big performance wins. It is still very easy to do something naively with poor performance. Also while the performance overhead is "high" it is orders of magnitude better than it was years ago. The overhead in terms of resources is tractable. RAM is inexpensive and so is CPU time compared to the cost of a single data breach both financially and in terms of user impact. :) My final comment on performance is that the way the code is generally structured it makes sense to do things in batches in parallel as opposed to doing individual atomic transactional data operations, but I think theres a lot of room to explore in the performance and optimization space. I think better reference examples, and a common platform to run examples on will foster the healthy exchange ideas and will help advance the art a lot. One of my personal goals for the toolkit is to provide people with demos to run (and with community help or a massive outpouring of interest and or funds to my benevolent corporate overlord), and help explore these tradeoffs using demos which are better than trivial complexity. Some computer scientist, software engineer, or applied mathematician might get interested in this subject and get hacking because we tried to make it easier to experiment. We know we COULD do a lot with this stuff (tons of applications or ways to use FHE), but few ARE doing things with this to solve real problems. Oh and if anyone wants, of course IBM can be contacted if you have a business problem you want to discuss, or need corporate education and such on these things. For non corporate folks, this toolkit gives EVERYONE access to some baseline reference technology. Stepping away from the corporate perspective, speaking as an individual and an individual and maintainer of the repo, soon I hope some more baseline educational materials if the community help engage with us to understand questions and better explain things. Reactions to this toolkit and inquiry from potential clients will really help us accelerate this work. Thanks for the continued interest in the hacker community and I wish we had time to respond to every interesting comment here!

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.
- dowem 6y ago
  Thanks for helping the conversation along jlokier! I thought since you mentioned the database concepts in your response you might be interested in checking the database example in our toolkit. It is really not a literal database but rather an in-memory key value search as that is easier to code and demonstrate. One of the nuances of FHE programming is that a full table scan is needed for cases like our database search because fundamentally we cant test and branch to bail out early when we find something we want. Key comparison to an encrypted search key are obviously not literal matches. Each has its own polynomial representation with its own error added to keep terms from encrypting to the same value every time. There is no way to compare for short circuit evaluation for instance. So we end up doing an operation on each value and effectively summing up those partial solutions in a way that lets us determine if a match was found. If anyone is interested let us know on our public slack channel and someone can answer more tech details there. You guys rock. Great questions and comments on this forum.
  - jlokier 6y ago
    Thanks for the enthusiasm and insights - and the toolkit of course! :-) > fundamentally we cant test and branch to bail out early when we find something we want I think this is derived from assumptions that are not necessarily valid, with a suitable representation in memory. In other words I think you can bail early without revealing too much, with a suitable data encoding. But after writing out a sketch of a mechanism in a HN comment I realised the idea may be patentable, and HME is probably an attractor for that sort of thing. (I also realise I may be full of nonsense, but you've got to start somewhere :-) I'm pretty open about ideas. An open source kind of person. But then I remembered, I posted something before and found someone else built on the idea and patented it (citing my post), stopping me from developing the idea. Yes, that happened, albeit a long time ago :-/ Hmm, uncomfortable.
    - betterunix2 6y ago
      "In other words I think you can bail early without revealing too much, with a suitable data encoding." Maybe, but whatever that is would not be encryption. An FHE scheme is still a public key encryption scheme, so it should not be possible to compute any predicate over the message without having access to the private key. The homomorphic property allows you to compute a new ciphertext that will decrypt to the result of a computation, but that new ciphertext will still completely hide the plaintext. Basically the reason you cannot "bail out early" is that FHE does not allow you to see an indicator value to tell you when to do so -- any such value would itself be encrypted. If it were not, then it would reveal "something" about the inputs; coupled with the fact that the inputs can always be modified (by e.g. changing the function that is being computed), that would be a complete break. The only good technique we have right now for addressing this problem is to use some kind of interaction between multiple parties, which allows sublinear random access and can allow branching (and thus early loop terminations etc.). There are cases where that works well and there are many real-world use-cases of those techniques (I work on this for a large tech company). The tradeoff is that you need to do a lot of communication, which is typically more expensive than computation, and if too many parties are offline the computation will not proceed (in the two party case nobody can be offline). You also need to trust the parties not to collude with each other, which is sometimes a concern in practice.
dowem 6y ago
(Reminder I am a maintainer of the toolkit and an IBMer, opinions are my own, etc. ) This is a pretty new field with people just starting to take it seriously for large problems. It seems from what I have seen in experiments, there can be big tradeoffs in latency against throughput and like most software, decomposing the problem and efficiently mapping it onto the underlying data structures gets the big performance wins. It is still very easy to do something naively with poor performance. Also while the performance overhead is "high" it is orders of magnitude better than it was years ago. The overhead in terms of resources is tractable. RAM is inexpensive and so is CPU time compared to the cost of a single data breach both financially and in terms of user impact. :) My final comment on performance is that the way the code is generally structured it makes sense to do things in batches in parallel as opposed to doing individual atomic transactional data operations, but I think theres a lot of room to explore in the performance and optimization space. I think better reference examples, and a common platform to run examples on will foster the healthy exchange ideas and will help advance the art a lot. One of my personal goals for the toolkit is to provide people with demos to run (and with community help or a massive outpouring of interest and or funds to my benevolent corporate overlord), and help explore these tradeoffs using demos which are better than trivial complexity. Some computer scientist, software engineer, or applied mathematician might get interested in this subject and get hacking because we tried to make it easier to experiment. We know we COULD do a lot with this stuff (tons of applications or ways to use FHE), but few ARE doing things with this to solve real problems. Oh and if anyone wants, of course IBM can be contacted if you have a business problem you want to discuss, or need corporate education and such on these things. For non corporate folks, this toolkit gives EVERYONE access to some baseline reference technology. Stepping away from the corporate perspective, speaking as an individual and an individual and maintainer of the repo, soon I hope some more baseline educational materials if the community help engage with us to understand questions and better explain things. Reactions to this toolkit and inquiry from potential clients will really help us accelerate this work. Thanks for the continued interest in the hacker community and I wish we had time to respond to every interesting comment here!