4 ms·

For the naive like myself, if FHE permits an untrusted computer to perform operations on encrypted data, without being able to read the unencrypted data, what o

For the naive like myself, if FHE permits an untrusted computer to perform operations on encrypted data, without being able to read the unencrypted data, what operations could be performed? (multiply/add?) Is it still capable of conditional logic? If so, how could this be done without unveiling some of the information? Edit: And what's even a good use case for it?

sa1 6y ago
Since conditional logic can be implemented as and/or logic gates, FHE should still apply to them and should be quite general purpose. But I’m not an expert, and I think it would depend on the design of specific FHE schemes.
- bawolff 6y ago
  I think there's a bunch of confusion between conditional logic in the sense of being able to solve a problem that can be specified with conditional logic, and the sense of having the performance implications of a normal program that has data-dependent branches.
  - sa1 6y ago
    I think FHE is nowhere close to practical performance, conditional branches or not.
moonchild 6y ago
> conditional logic Conditional logic can be expressed in terms of arithmetic: if c then t else f = c*t + (1-c)*f You can also do boolean logic: NOT y = 1 - y x AND y = x * y x OR y = (x + y) - (x * y) (Where 1 indicates truth and 0 falsity.) What you can't do, however, is conditional execution, as this would leak information. Which doesn't limit the capabilities of the system in principle, but does in practice because this harms performance. E.G. ‘select count(*) from users where name = bob’ will be much slower with HFE than with a traditional database because there will be no possibility of using precalculated indices.
- h0l0cube 6y ago
  Ah yes, I was thinking it was possible to execute both computations and take the one you need. 'Conditional execution' was more what I meant.
doomrobo 6y ago
You can think of FHE as just "you can compute arbitrary polynomials over ciphertexts". You can't exactly get conditional execution using polynomials. Most people instead think of FHE computation as "arithmetic circuits". Also, some schemes offer extra stuff for free. BFV (https://eprint.iacr.org/2012/078 https://eprint.iacr.org/2012/078) for example lets you compute Frobenius endomorphisms very cheaply. That is, given ciphertext c, you can compute c^q without having to do log(q) many squarings, where q is the characteristic of your ring.
- h0l0cube 6y ago
  Can you think of a practical use for something like this? Perhaps there's a need to keep an algorithm secret, but also the client wishes to keep their inputs secret?
  - bawolff 6y ago
    > Perhaps there's a need to keep an algorithm secret, but also the client wishes to keep their inputs secret? That is basically the problem statement that FHE is trying to solve.
  - doomrobo 6y ago
    Yup that's the idea. I give an example in another comment https://news.ycombinator.com/item?id=26421172 https://news.ycombinator.com/item?id=26421172
numpad0 6y ago
FHE was pursued by Japanese telcos pre-2000s. Imagine a central exchange building, serving few million customers in a region, each connecting from VT110 over ISDN line, handling imagined Internet thing pre-Internet. Something like “Tanaka-san is making a golf course reservation using easy to learn SQL language”. FHE-based database fits the bill there; there’s a risk that equipment technicians might get hold of a key. FHE can offer protections all-around. Performances and privacy of logic is irrelevant; it’s responsibilities of service providers to account for technical implications. Code to run is supplied. Customers are not required to/expected to write it. Researchers doing FHE works today would be fully aware of Internet, but models in some papers to explain it might still carry that Transatlantic accent.
- h0l0cube 6y ago
  > Code to run is supplied. Customers are not required to/expected to write it. Do I have this right: FHE is useful for running queries across a dataset without revealing what the queries are nor the result? If so, would write operations even be possible?
  - osaariki 6y ago
    I do research on FHE. On a high level querying works by evaluating an equivalence function between the encrypted query key and keys in the database such that the result is 1 if the key matches and 0 otherwise. You can then multiply this with the values and sum all of them together to get just the row that matches. For write operations you could do a similar trick to select a new version of each value based on the query key matching. You are in effect writing all rows, but using the old value when you don't want to change it. Now, due to some quirks of FHE you can only do this write operation a limited number of times before you have to perform a more expensive operation called bootstrapping to "refresh" ciphertexts. I find bootstrapping to be the coolest part of homomorphic encryption: you encrypt the secret key itself with homomorphic encryption and then use it to decrypt inside FHE. The result is still encrypted but closer to a freshly encrypted ciphertext.
    - jdc 6y ago
SilasX 6y ago
Yes, multiply and add, or any set of operations necessary to create an arbitrary Boolean function, which then would have encrypted input and output. From that you get "Turing completeness" because, for any computation you want to do, you can unwind it into a static Boolean circuit that computes (some appropriately sized version of) it. Note that this means you're limited to primitive recursive functions i.e. all loops must be compile-time bounded. The use case is stuff like, "add up my numbers without knowing what the numbers are or their sum is". I think there are also end-to-end auditable voting systems that preserve privacy.
parksy 6y ago
From my understanding, FHE can represent Boolean circuits, so you don't write an "FHE application"; you can send an encrypted input into an encrypted Boolean circuit and get an encrypted result. Since FHE operations are Boolean circuits, we can consider basic stuff like "AND" or "NOT" - but all the inputs, outputs and the operation itself are encrypted, so the owner of the server won't even know if someone called an AND gate, a NOT gate, or something else. Which means that if primitive Boolean operations are supported, you can chain them to create a general purpose, Turing complete computer. However if you were a nefarious actor looking at the order and frequency at which various primitives were called, then you could be able to discern a call graph (or at least, a statistical "heatmap"), and you might figure something about the nature of the program, and therefore be able to glean some kind of understanding of the information passing through it, however abstract. However since FHE can represent boolean circuits, we're not just limited to primitives. A futuristic compiler could create a single boolean circuit to represent a complex application - however for something like a blog or eCommerce store, that would result in inordinate amount of cyphertext to represent the code, and undoubtedly be very slow to run. I think more likely is the compiler would optimise layers or stacks of black-boxes that are not simply boolean primitives. Your plaintext code (in the language of you choosing) would have every branch of the call stack from input, processing, and output analysed n-levels deep optimising for a balance of runtime and obfuscation. In such a case, the nefarious actor would see a blob of cypher going into a blob of other cypher to generate a blob of cypher as input into the next blob of cypher. Maybe there are parallel cypher blobs, but their internals are completely hidden. An inside actor might have intimate knowledge of how long each blob takes to execute for various inputs, so assuming that knowledge is shared we're back at good old timing attacks - which would probably become irrelevant on the next compiler pass anyway. Use-cases I can think of are any kind of transactional situation where various actors have competing interests, where it may be in one or more actor's best interests to game the system. Anything peer-to-peer is a good example. Gaming seems trite, but in the early days, gaming was full of client side cheats. The current model for multiplayer gaming to avoid cheating is centralised - every client has to interface with a central server that then has to figure out which moves were legal in the game's rules - peer-to-peer is fraught with cheaters since they can analyse and change the code client-side. Realtime FHE would allow game developers to come back to peer-to-peer gaming, since it would be mathematically improbable that a peer is cheating. Escrow is another peer-to-peer type activity, where it would be useful to have a trusted middleman. Maybe provenance for digital / physical goods (that's a bit of a stretch). But essentially, right now, a lot of development effort is expended to make sure individuals in a system can't gain an advantage on the client side - if we didn't have to trust a user's computer to do the right thing, then the client/server trust barrier collapses.

sa1 6y ago

Since conditional logic can be implemented as and/or logic gates, FHE should still apply to them and should be quite general purpose. But I’m not an expert, and I think it would depend on the design of specific FHE schemes.

bawolff 6y ago
I think there's a bunch of confusion between conditional logic in the sense of being able to solve a problem that can be specified with conditional logic, and the sense of having the performance implications of a normal program that has data-dependent branches.
- sa1 6y ago
  I think FHE is nowhere close to practical performance, conditional branches or not.

moonchild 6y ago

> conditional logic Conditional logic can be expressed in terms of arithmetic: if c then t else f = c*t + (1-c)*f You can also do boolean logic: NOT y = 1 - y x AND y = x * y x OR y = (x + y) - (x * y) (Where 1 indicates truth and 0 falsity.) What you can't do, however, is conditional execution, as this would leak information. Which doesn't limit the capabilities of the system in principle, but does in practice because this harms performance. E.G. ‘select count(*) from users where name = bob’ will be much slower with HFE than with a traditional database because there will be no possibility of using precalculated indices.

h0l0cube 6y ago
Ah yes, I was thinking it was possible to execute both computations and take the one you need. 'Conditional execution' was more what I meant.

doomrobo 6y ago

You can think of FHE as just "you can compute arbitrary polynomials over ciphertexts". You can't exactly get conditional execution using polynomials. Most people instead think of FHE computation as "arithmetic circuits". Also, some schemes offer extra stuff for free. BFV (https://eprint.iacr.org/2012/078 https://eprint.iacr.org/2012/078) for example lets you compute Frobenius endomorphisms very cheaply. That is, given ciphertext c, you can compute c^q without having to do log(q) many squarings, where q is the characteristic of your ring.

h0l0cube 6y ago
Can you think of a practical use for something like this? Perhaps there's a need to keep an algorithm secret, but also the client wishes to keep their inputs secret?
- bawolff 6y ago
  > Perhaps there's a need to keep an algorithm secret, but also the client wishes to keep their inputs secret? That is basically the problem statement that FHE is trying to solve.
- doomrobo 6y ago
  Yup that's the idea. I give an example in another comment https://news.ycombinator.com/item?id=26421172 https://news.ycombinator.com/item?id=26421172

numpad0 6y ago

FHE was pursued by Japanese telcos pre-2000s. Imagine a central exchange building, serving few million customers in a region, each connecting from VT110 over ISDN line, handling imagined Internet thing pre-Internet. Something like “Tanaka-san is making a golf course reservation using easy to learn SQL language”. FHE-based database fits the bill there; there’s a risk that equipment technicians might get hold of a key. FHE can offer protections all-around. Performances and privacy of logic is irrelevant; it’s responsibilities of service providers to account for technical implications. Code to run is supplied. Customers are not required to/expected to write it. Researchers doing FHE works today would be fully aware of Internet, but models in some papers to explain it might still carry that Transatlantic accent.

h0l0cube 6y ago
> Code to run is supplied. Customers are not required to/expected to write it. Do I have this right: FHE is useful for running queries across a dataset without revealing what the queries are nor the result? If so, would write operations even be possible?
- osaariki 6y ago
  I do research on FHE. On a high level querying works by evaluating an equivalence function between the encrypted query key and keys in the database such that the result is 1 if the key matches and 0 otherwise. You can then multiply this with the values and sum all of them together to get just the row that matches. For write operations you could do a similar trick to select a new version of each value based on the query key matching. You are in effect writing all rows, but using the old value when you don't want to change it. Now, due to some quirks of FHE you can only do this write operation a limited number of times before you have to perform a more expensive operation called bootstrapping to "refresh" ciphertexts. I find bootstrapping to be the coolest part of homomorphic encryption: you encrypt the secret key itself with homomorphic encryption and then use it to decrypt inside FHE. The result is still encrypted but closer to a freshly encrypted ciphertext.
  - jdc 6y ago

SilasX 6y ago

Yes, multiply and add, or any set of operations necessary to create an arbitrary Boolean function, which then would have encrypted input and output. From that you get "Turing completeness" because, for any computation you want to do, you can unwind it into a static Boolean circuit that computes (some appropriately sized version of) it. Note that this means you're limited to primitive recursive functions i.e. all loops must be compile-time bounded. The use case is stuff like, "add up my numbers without knowing what the numbers are or their sum is". I think there are also end-to-end auditable voting systems that preserve privacy.

parksy 6y ago

From my understanding, FHE can represent Boolean circuits, so you don't write an "FHE application"; you can send an encrypted input into an encrypted Boolean circuit and get an encrypted result. Since FHE operations are Boolean circuits, we can consider basic stuff like "AND" or "NOT" - but all the inputs, outputs and the operation itself are encrypted, so the owner of the server won't even know if someone called an AND gate, a NOT gate, or something else. Which means that if primitive Boolean operations are supported, you can chain them to create a general purpose, Turing complete computer. However if you were a nefarious actor looking at the order and frequency at which various primitives were called, then you could be able to discern a call graph (or at least, a statistical "heatmap"), and you might figure something about the nature of the program, and therefore be able to glean some kind of understanding of the information passing through it, however abstract. However since FHE can represent boolean circuits, we're not just limited to primitives. A futuristic compiler could create a single boolean circuit to represent a complex application - however for something like a blog or eCommerce store, that would result in inordinate amount of cyphertext to represent the code, and undoubtedly be very slow to run. I think more likely is the compiler would optimise layers or stacks of black-boxes that are not simply boolean primitives. Your plaintext code (in the language of you choosing) would have every branch of the call stack from input, processing, and output analysed n-levels deep optimising for a balance of runtime and obfuscation. In such a case, the nefarious actor would see a blob of cypher going into a blob of other cypher to generate a blob of cypher as input into the next blob of cypher. Maybe there are parallel cypher blobs, but their internals are completely hidden. An inside actor might have intimate knowledge of how long each blob takes to execute for various inputs, so assuming that knowledge is shared we're back at good old timing attacks - which would probably become irrelevant on the next compiler pass anyway. Use-cases I can think of are any kind of transactional situation where various actors have competing interests, where it may be in one or more actor's best interests to game the system. Anything peer-to-peer is a good example. Gaming seems trite, but in the early days, gaming was full of client side cheats. The current model for multiplayer gaming to avoid cheating is centralised - every client has to interface with a central server that then has to figure out which moves were legal in the game's rules - peer-to-peer is fraught with cheaters since they can analyse and change the code client-side. Realtime FHE would allow game developers to come back to peer-to-peer gaming, since it would be mathematically improbable that a peer is cheating. Escrow is another peer-to-peer type activity, where it would be useful to have a trusted middleman. Maybe provenance for digital / physical goods (that's a bit of a stretch). But essentially, right now, a lot of development effort is expended to make sure individuals in a system can't gain an advantage on the client side - if we didn't have to trust a user's computer to do the right thing, then the client/server trust barrier collapses.