3 ms·

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

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.
    - jlokier 6y ago
      > 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 It depends what you're doing. If the idea is to search for a value in an encrypted list to see if it's there, or lookup a value in a key-value store, that's similar to a database query. Unencrypted, that can be performed in a hard-bounded sublinear time, so encrypted, the steps can also be sublinear without revealing content to the processor, if there is a way to calculate the addresses in each step homomorphically, i.e. without the processor knowing the meaning of those addresses, just calculating them from data it sees. That's where the encoding comes in, storing the data in such a way that knowing individual encrypted addresses doesn't reveal much about the data, and depending on what properties are important to you, also in such a way that access pattern structure such as repetition is also hidden because the addresses for encrypted access are not repetitive. This requires the encoding to do some level of data diffusion. Branching is also not ruled out if the processor can't determine whether a branch has occurred. That means although the processor cannot determine when a search is short-circuited, the result of the search may still be used "early" by later stages in the homomorphic calculations, provided this does not look like a branch to the processor. Think of predicated instructions. > The only good technique we have right now for addressing this problem is to use some kind of interaction between multiple parties, That's not what I have in mind, but there's some similarity. I imagine each memory having some dedicating processing on board, just to reduce communication overhead during writes, which are heavy due to data diffusion.

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.
  - jlokier 6y ago
    > 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 It depends what you're doing. If the idea is to search for a value in an encrypted list to see if it's there, or lookup a value in a key-value store, that's similar to a database query. Unencrypted, that can be performed in a hard-bounded sublinear time, so encrypted, the steps can also be sublinear without revealing content to the processor, if there is a way to calculate the addresses in each step homomorphically, i.e. without the processor knowing the meaning of those addresses, just calculating them from data it sees. That's where the encoding comes in, storing the data in such a way that knowing individual encrypted addresses doesn't reveal much about the data, and depending on what properties are important to you, also in such a way that access pattern structure such as repetition is also hidden because the addresses for encrypted access are not repetitive. This requires the encoding to do some level of data diffusion. Branching is also not ruled out if the processor can't determine whether a branch has occurred. That means although the processor cannot determine when a search is short-circuited, the result of the search may still be used "early" by later stages in the homomorphic calculations, provided this does not look like a branch to the processor. Think of predicated instructions. > The only good technique we have right now for addressing this problem is to use some kind of interaction between multiple parties, That's not what I have in mind, but there's some similarity. I imagine each memory having some dedicating processing on board, just to reduce communication overhead during writes, which are heavy due to data diffusion.