The killer thing is the performance penalty for doing FHE on any dataset of meaningful size. This is because if you want to do an operation on one member of the set you need to do an operation on all members of the set otherwise you leak which member you care about. For sets of a very small size this performance penalty might be ok. For sets of a large size, like the set of all users of a service, the performance penalty will grow at least linearly to the size of the set.

This is the problem at the core of ZK-style proving systems. You can push the proof construction work into the client and have a sub-linear verification time relative to the proof, but the proof construction in the first place is going to be slow and expensive (and slower as the size of the set increases!).

The edge of research here is being done by cryptography labs all around the world. If someone does manage to solve this in a purely-software based manner with a performance penalty that is acceptable for a monotonically increasing set, that’s the holy grail. I remain unconvinced that this will be solved in a reasonable fashion for this use case in my lifetime (but I would be thrilled to be proven wrong!!). If you know of research which makes inroads on this problem, please point me at it.

In all of the use cases you have mentioned, FHE machine on the user device, can not perform interactions(IO, etc..) with the outside world (can't connect to a network, can't display things on a screen, etc..) without the key. So for these devices to be useful, the keys will have to be embedded in the IO paths(in which case the device would be hackable) or FHE machine should be implemented as subsystem that does things like DRM(I'm not sure if this would be possible either, but it could be).

I might be completely wrong here, but can someone sketch out how FHE can be used to make an unhackable consumer device?

I'm also seeing some questions over side channel attacks by throwing enough data at the polynomial transforms that make up the NAND gate you're hiding the FHE'd data in, some people are claiming there has to be a way to eventually derive the encrypted value of the data you're attacking, but I don't understand any of the maths around FHE so I can't tell how big a concern those types of attacks are. From my layman's interpretation of the comments IBM'ers are responding to, I don't think a single operation under FHE is intrinsically vulnerable to side channel attacks, but I bet how FHE is used in real-world applications with iterative back-and-forth operations does potentially open up specific poorly-designed usage patterns to the classic inferential side channel attacks.

If FHE becomes practical at the scale you imagine, it would dramatically raise the bar on hacking for sure, but the implementers still only need to make one mistake to give a wedge to the hackers to work with.

The tokenization market (tokenize/detokenize sensitive data) just turned up the "interesting" knob to 11, though. Would take a lot of work between vendors to make real and practical, but some real promise there.

What I hoped for is that FHE would usher in the era of more end-user control over the data, not less off it. That's because it would allow to decouple and isolate storage from compute, in such a way that I could invite company's code to process my data, encrypted by me, at the location of my choosing, and the code would have no way to exfiltrate the data. At the same time, I would have no way to get at the service company's software. I somehow never realized it would be easier for software providers to just skip the "my data at my location" part, and just force us to use their FHE software while also owning the data entered into it.

I'm of the understanding that you send me ciphertext, I transform it with some operations you define, and I send back ciphertext-v2.

I can discern how this could exfiltrate data safely. They send in a bunch of zeros and I fill in a one for each minute I used this lightbulb, by dynamically creating the FHE circuit to reflect the data saved.

It's not clear to me how this could change my lightbulb. By 'change' I mean 'affect the behavior' or update the firmware or something. I say this with the expectation that the blobs I received and produced are ciphertext on my side, without keys to decrypt it (unlike, say, dvd drm).

And locally unreadable.

Now you can run the FHE step for as many times as the algorithm requires, giving you a FHE-VM that can execute any WebAssembly program from your favorite Turing complete programming language.

The limitations are that you need to define a bounded machine state, which technically breaks the Turing completeness. In practice this is no different from your laptop having a finite amount of memory which disqualifies it as a Turing machine. Real Turing machines don't exist.

The other limitation is that the FHE executor can now see the total run time of the algorithm, which was secret before. This is similar to a timing side channel and similar mitigations apply.

As others have pointed out, if you have a concrete algorithm you can do something much simpler than implement a VM. The Collatz sequence is good toy example of an algorithm with unknown loop bounds. You would make a FHE circuit that iterates a single step using the same overall design.

FHE is equivalent to circuits, i.e., every circuit has a representation as a FHE. I feel like the idea is: Circuits can perform arbitrary computations on a limited size input, but not on an arbitrary size inputs. Loops are not a problem, as they are an implementation detail. Unbounded output is not possible on a touring machine that halts for all inputs of size s limited by some constant. There exists a circuit that would compute the same thing, as you can take the (binary encoded) results of the touring machine and just create a truth table from that, which describes a circuit. Circuits are interesting because they are usually limited in size.

So you compile your program into a circuit of a fixed size and can then compute solutions of this size. If you are interested in larger problems, you compile your program into a larger circuit. E.g., a function returing an 32bit integer and taking 20 32bit integers as parameters can be represented this way (without infinite loops, but those aren't covered by turing machines either), no matter the computation within that function.

edit: correction, obviously a circuit can not represent all partial functions, only functions (i.e., all inputs have an output).

Consider the following conventional code:

  if (flag) {
    a = b + c
  } else {
    a = b * c
  }

  a =  flag * (b+c) + (1-flag) * b * c

Result has no bit set = both terms equal Result's sign bit is set = second term bigger Result's sign bit isn't set = first term bigger

Multiplying by the result of comparisons (aka 0 and 1, as you state) is actually a common performance optimization. Does not work for everything, but when it works it works well.

(ANDs and XORs are just multiplication and addition over bits, and we build comparisons out of these all the time.)

Re: the ability to do control flow, you can implement your Turing machine automaton as a circuit easily, and can then evaluate that using FHE

- If the program is meant to run forever, or as long as possible, then the system performing the computations can drive the loop. This might be useful for anytime algorithms (e.g. an AI/optimisation problem): e.g. "keep iterating this computation (unless my billing account runs out of credit), I might ask for the current state at some point in the future".

- Programs which eventually halt could be checked by the key holder: the result gets decrypted, and if it isn't in the 'halt' state then it's sent back for another 'step'. In practice this could be made more efficient by e.g. making the computation idempotent, so it can be iterated many times without having to ask for confirmation every time; by having the encrypted computation perform many iterations, so each 'step' does more work; etc. If the job is kept on the encrypted system, with the key holder sending it step/stop instructions, that leaks details of the computation (i.e. an upper-bound on how many steps it takes). If we're willing to round-trip the data instead, then the key-holder can re-encrypt it each time (and jitter its timings), so the server couldn't tell the difference between stepping the same job and computing multiple jobs. This could be further obfuscated by throwing our jobs into a pool of others, e.g. on a shared proxy.

This model of having some external entity "driving" a computation's loop appears in a few other places too:

- Smart contracts, like Ethereum, give programs "fuel" that decreases with each step, and calling another program requires us to give it some of our fuel.

- Optimisation algorithms can also use "fuel" to avoid infinite loops. Some compilers use this to avoid transformations getting stuck in a cycle (rewriting the code between one form and another).

- Total (functional) programming languages, like Agda and Coq, don't allow general recursion; yet they do allow co-recursion. This lets us wrap each recursive call (i.e. step) in a constructor, then we can "drive" the program by having an external program unwrap these constructors (AKA a main loop).

- Coq's Mtac language lets us use general recursion in our proofs, but the results get wrapped up (just like the co-recursive example above). The compiler will run these proofs to completion: if they don't halt then neither does the compiler.

- CSS can be "driven" by user clicks, which together become Turing complete: https://notlaura.com/is-css-turing-complete

That's not to say that a badly-designed usage of homomorphic computation can't introduce a timing channel, though. If there's a point in time where the result is handed back to the client, they inspect it, and then conditionally send more computations, you might be able to infer something with either the client's timing or if they happened to send back more computations or not. However, that assumes that we'd be able to trace multiple API requests associated with the same data set (as opposed to unrelated computations), and that we know enough about the computations we're being told to do to infer a timing channel from them. That's why I use the qualifying term "badly-designed", which in practice will probably be most uses of this technology.

Yes, FHE is not (currently) good at general-purpose computing. Complex conditional logic for example is a non-starter because every branch has to be evaluated. But tensor multiplication is well supported with existing FHE schemes, and many kinds of machine learning tasks consist of non-conditional tensor multiplications.

It will also allow organizations to train models collaboratively in a privacy preserving way, which if you think about it has lot of consequences.

Which both are probably untrue assumptions :-)

MPC introduces a trust assumption. MPC is only private if some threshold of the multiple parties are honest and destroy their secrets. Though often this threshold is just one, efficient MPC often only has 3 participants total.

FHE gives you a better security model than either of these, as it neither relies on physics for safety nor needs to assume any level of honesty from the person running the computation.

As the comments in the article state, it's actually all done with operations on polynomials with encrypted coefficients. As + and x can be done on polynomials, it all works out.

The maths behind it is of course much more complicated.

As for a simple maths analogy, consider adding 1 + 2.

I'll encrypt your values by multiplying by 3 mod 7. So encrypt(1) = 3x1 mod 7 = 3 mod 7 and encrypt(2) = 3*2 mod 7 = 6 mod 7. Only the encrypted values are sent, along with the operations I want to perform on the values.

Now this scheme is homomorphic, as I can just add the encrypted values, encrypt(1) + encrypt(2) = 3 + 6 mod 7 = 2 mod 7. That is the only computation that would be done before sending back the result.

To decrypt it, I would have to divide by 2 mod 7 by 3, which gives me 3 (you can easily check that encrypt(3) = 2 mod 7). And indeed 1 + 2 = 3. So the decrypted answer is correct.

Of course this scheme is too easy to crack. The FHE scheme is not.

If we keep up the trend (big if) this is actually quite promising

> protected from anyone except very few who could extract private key from secure chip

The way I understand chip manufacturing it would be hard to diffuse a separate key into each chip. This means it'd only take one of those very few people to extract and leak the key (or cut out the middleman and leak it from inside AMD) to break it for everyone.

> The only real world issue would be side channel attacks.

This is probably a much bigger problem in practice. Spectre & related attacks have been effective against Intel SGX[2], another "trusted environment" inside a larger system.

[1]: https://developer.amd.com/sev/ [2]: https://arstechnica.com/gadgets/2018/08/intels-sgx-blown-wid...

…and Intel. This has obvious problems in who the root of trust should be, as well as putting all the eggs in the same basket.

Also, what you propose is I think equivalent to the SEV technology mentioned in the article.