...but, if you interleave your Brainfuck program with, say, (classical) encryption of a canary constant, then you can check the canary constant when you decrypt the result, and you have high assurance that the computation is genuine - an attacker couldn't distinguish canary operations from real code, though you'd have to scatter the output bytes uniformly in the output. This scheme is a bit like obfuscation inside FHE.
- Is there a more efficient way to securely tamper-proof your results?
- How robust is this (or your own) scheme against a small number of adversarial bit flippings?
(Note that adversaries can mutate arbitrary bits via BlindRotate() in NuFHE/other TLWE schemes, they just can't extract the plaintext value (though they can set it, for example by NANDing.)
So we don’t necessarily have to create an entire VM to, say, run a FHE machine learning model. That can be built directly and specifically optimized for the task. I think that’s where this is currently useful for real world stuff.
>This means you can multiply together any two Elgamal ciphertexts, and upon decryption you’ll find that the (single) resulting ciphertext now embeds the product of the two original plaintexts. Neat!
Coolest thing I've read in a while.
So... efficient computing with homomorphic encryption should focus on branch-free programming on CISC architectures with a huge number of instructions?
> This is because at every cycle, the VM has to go through every possible instruction on every possible data cell.
We have a couple of variables: the data pointer, the instruction pointer
The values of these are encrypted BUT we can change them by performing logical operations (AND, OR, XOR, etc) on them.
So a cycle of the VM asks
1. Is the current instruction the correct instruction?
2. Is the current data cell the correct data cell?
Obviously if we knew the value of the instruction pointer we could just go straight to the correct instruction, and if we knew the index of data cell I could go straight to it.
The problem is that we don't know either of these things. So we have to go to every instruction and every data cell and check if it's the correct one. If it is then we can perform the instruction, otherwise we move on.
You can see now why this would be slow too. It's even slower though because in order to do this "check" we have to execute logic gates and the gates can take ~0.8 seconds (on a somewhat modern CPU).
1. Random access (reading input-dependent memory address) must be simulated with linear scans of the array.
2. Input-dependent branches must be transformed as follows: both branches are evaluated, and the side effects must be combined using the branch condition (e.g. x <- xc + new_x(1-c)).
3. Loops with input-dependent bounds must be unrolled to their maximum number of iterations (this is not always easy to compute).
In general you would probably write your programs in a special-purpose language that is easy to compile for this model of computation. Efficiency can suffer for some algorithms -- sorting winds up being O(n lg^2 n) instead of O(n lg n), for example.
Also the best FHE schemes are still nowhere near practical for the majority of computations people care about.