9 ms·
The comment by "Ibmresearcher" says that: > Once one can do multiplication and addition all other operations can be bootstrapped from there so you can indeed d
by giomasce 6y ago
The comment by "Ibmresearcher" says that:
> Once one can do multiplication and addition all other operations can be bootstrapped from there so you can indeed do anything a Turing complete computer can do.
This is apparently iterated on many articles about FHE, but it seems false to me: to do Turing-complete stuff you also need comparisons, and the ability to change your flow depending on comparisons. But clearly you cannot do that with FHE, otherwise you could extract the encrypted content, one bit at a time.
My understanding is that an FHE computer can only execute a fixed net of additions and multiplications (or whatever operations they've got). So you can emulate an "if" clause by computing both branches and then selecting one of the two multiplying by 0 and 1 appropriately; you can do bounded "for" loops always executing the maximal number of times, but you can't do unbounded loops, therefore bye bye Turing completeness.
Of course there are a lot of interesting algorithms that can be executed without being Turing complete, but the general statement is false. Am I missing anything?
- _trampeltier 6y agoCode might finaly look like with movfuscator (MOV on a intel processor is also turing complete).
- giomasce 6y agoNo, it can't. FHE cannot emulate the whole MOV, especially the features that make it Turing-complete.
- jchw 6y agoThe reason why Intel mov is so powerful is because the mnemonic actually maps to tons of different things. In particular conditionals are accomplished using indirect memory accesses.
- SilasX 6y agoMovfuscator only works because x86's MOV is like the Swiss Army knife of move instructions. It doesn't just copy bits from one location to another, but has parameters for conditionality and arithmetic, which is what allows it to be so general. That still doesn't address the parent's confusion (that I share) of how you get Turing-completeness just from addition and multiplication.
- dlubarov 6y agoTrue, but there are simpler (abstract) machines that also achieve Turing completeness: https://en.wikipedia.org/wiki/One-instruction_set_computer https://en.wikipedia.org/wiki/One-instruction_set_computer > That still doesn't address the parent's confusion (that I share) of how you get Turing-completeness just from addition and multiplication. I wouldn't say arithmetic circuits are Turing complete since they can only perform bounded computations, but we could say that they're functionally complete. It is known that boolean AND and OR gates are functionally complete, and we can reduce them to multiplication and addition in any finite field: x and y = x * y x or y = ¬(¬x and ¬y) = 1 - (1 - x)(1 - y)
- giomasce 6y agoWhat does "functionally complete" means for you?
- dlubarov 6y agoInformally, I mean reducible from time-bounded Turing machines. Given a Turing machine TM and a time bound T, a (binary or arithmetic) circuit can be constructed to simulate TM for T steps. Or in other words, a circuit can be constructed to solve any particular instance of FNTIME(T).
- rrobukef 6y agoYou get bounded-Turing completeness. This is sufficient for all practical applications as we live in a finite universe.
- cameron76 6y agoPersonal pet peeve that whenever someone brings up the movfuscator, all the responses seem to of the “well akshhhhuallly...” variety, I’ve never understood it. The responses here are generally incorrect; x86 mov does not have conditionals (that would be ccmov), cannot load the program counter, and can’t do general arithmetic beyond very standard indirect addressing ( the same forms allowed by many RISC architectures). movfuscator actually includes a version that uses only two forms of mov (a load and store form) that would work on nearly any common RISC architecture. So the assertions that “this only works because x86 mov is ___” are generally incorrect, and needlessly dismissive of an interesting idea - the addressing used by movfuscator is just addition/subtraction. Certainly at least, at a broader level, the idea that it may be desirable to reduce general computation to some extremely simple form is interesting.
- krasin 6y agoin FHE you need to execute all branches, but the result could be just like you executed the right one. Consider the following conventional code: if (flag) { a = b + c } else { a = b * c } In FHE it could look: a = flag * (b+c) + (1-flag) * b * c That way, you can express almost arbitrary programs. I don't make a claim that a Turing machine could be, though.
- rocqua 6y agoThe big question isn't branching, it's unbounded loops. It seems to me the only option is unrolling those loops. But that has a massive performance penalty. Because you need to always run through however deep you unrolled.
- giomasce 6y agoYou can't unroll an unbounded loop, you don't know how many times to unroll. To have Turing machine you need to need to know from your program state if you reached the end of your loop or not (i.e., you need to evaluate the "while" condition), and by definition FHE shouldn't allow you to extract information from your program state.
- IshKebab 6y agoYou can unroll a sufficient number of times. There would be an upper limit on iterations and it would presumably be horrible inefficient, but I can't see why it wouldn't work.
- layer8 6y agoIf you know how many iterations are sufficient, the unbounded loop could have been written as a bounded loop in the first place. For truly unbounded loops, you’re still stuck.
- IshKebab 6y agoI mean, that's the same as saying no computer is Turing complete because it doesn't have infinite memory. I'm not saying it is a practical solution to unroll a loop that might run a billion times.
- ogogmad 6y agoTo summarise the other comments: No, it's not actually Turing complete. The programs you can express using circuits have a fixed running time.
- SilasX 6y agoOh. But FHE means Turing-complete, right? So what else do they have besides addition and multiplication that allows them to do arbitrary computations?
- ogogmad 6y agoFHE just means that you can do addition and multiplication on ciphertexts. The ability to do that implies that you can build logical circuits. Those logical circuits are highly expressive, but not Turing complete.
- SilasX 6y agoThe definition of FHE specifies arbitrary computation: https://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_Homomorphic_Encryption https://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_H... If it's really just addition and multiplication, it's not FHE.
- ogogmad 6y agoI think the Wikipedia page is oversimplifying somewhat at the cost of accuracy.
- SilasX 6y agoWeird, feels kind of misleading just on general principle to call it "fully" when it doesn't do the full set of computations. I found this link [1] which makes this distinction: > Partially Homomorphic Encryption (PHE): In PHE scheme, only one type of mathematical operation is allowed on the encrypted message, i.e., either addition or multiplication operation, with unlimited number of times, > Somewhat Homomorphic Encryption (SHE): In SHE, both addition and multiplication operation is allowed but with only a limited number of times. > Fully Homomorphic Encryption (FHE): FHE allows a large number of different types of evaluation operations on the encrypted message with unlimited number of times. And even then, multiplication is just repeated addition, so it still feels off to say it goes beyond partially homomorphic in the above schema. (Edit: actually, for arbitrary inputs, you can't reduce it like that, so ignore this para.) In any case, original claim from the article that started this thread [2] is wrong. [1] https://www.sciencedirect.com/topics/computer-science/fully-homomorphic-encryption https://www.sciencedirect.com/topics/computer-science/fully-... [2] "Since all mathematical and logical operations can be built from additive and multiplicative operations, "
- MrYellowP 6y agoComparisons can be done via subtraction. 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.
- giomasce 6y agoYes, but you can't branch on the result, because you don't know if the result is zero or not. So your program needs to have fixed control flow, i.e., you cannot implement arbitrary programs.
- dlubarov 6y agoThere isn't branching in the traditional sense, but we can work around it. Instead of doing result = if condition { a } else { b } in circuit programming, we normally do result = condition * a + (1 - condition) * b
- giomasce 6y agoSure, that was already mentioned on another comment, but that's not enough for proper branching. You also need while loops. See also comment https://news.ycombinator.com/item?id=24018284 https://news.ycombinator.com/item?id=24018284.
- heavenlyblue 6y agoIf you constrain your computer to always take the same amount of time to execute any while loop (which a homomorphic computer needs to do not to leak any data), your computer would also have unbounded circuitry complexity and thus it’s not any better. Also unbounded loops can’t practically finish even on a Turing machine :)
- giomasce 6y ago
- ketzu 6y agoAfter putting some thought into this during a deeper comment chain somewhere, I thought about it this way: 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).
- giomasce 6y agoNo, you cannot convert an arbitrary Turing machine to a circuit. Not even if you assume a bounded input size. Not even if you assume just one single allowed input, because you might not be able to know if that Turing machine ever terminates on that input. And loops are not an implementation details. Bounded loop are, one might argue, an implementation detail, but unbounded loops are precisely _the_ problem: in general it is impossible, given an arbitrary Turing machine (or an arbitrary C, Python, whatever Turing-complete language program), to give an upper bound on the number of iterations its loops will require.
- ketzu 6y agoSeems like I didn't put enough thought into it and my computability class has been too long ago! In hindsight it's kind of obvious: All functions computed by circuits must be a function an can not be a partial function, because a circuit can't output nothing.
- 6y ago
- chriswarbo 6y agoAny program can be compiled to a single `while` loop with a `switch`. I can think of two ways to "drive" this `while` loop: - 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 https://notlaura.com/is-css-turing-complete
- giomasce 6y agoI agree. These are totally legitimate ways to still use FHE even if you need to compute a Turing-complete thing. It doesn't thwart my theoretical point, because you're not doing pure FHE anymore: you're using FHE for the "Turing-incomplete" part of your algorithm, plus some external oracle to check for termination. Practically this might still be an acceptable way to tackle the problem. I mean, "practically" as much as FHE itself is.
- Ar-Curunir 6y agoYou can implement comparisons using addition and multiplication (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
- remcob 6y agoImagine a FHE circuit that executes a single webassembly instruction. This is a finite circuit that takes as input the program, machine state and external input (all encrypted). As output it returns the (encrypted) new machine state and a single unencrypted bit indicating if the program terminated or not. 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.
- giomasce 6y agoTotally agree. Just let me point out that this is not, theoretically speaking, an FHE computation. It is an "FHE plus a termination oracle" computation. Maybe no big difference in practice, but totally a different thing in theory, which was the point of my comment.
- benlivengood 6y agoThis is basically all that modern computers are; a giant circuit and a clock to keep sending a "do the next thing" signal. Is it a stretch to say that "1: perform this list of multiplications and additions. 2: GOTO 1" cannot be called a FHE system?
- SilasX 6y agoBut modern computers let you send them instructions entirely in a Turing-complete language, with no requirement that you first know how to unroll them into a static circuit (constant-bounding every loop). That seems like a bigger difference than "oh sometimes you get out-of-memory errors".
- R0b0t1 6y agoQuick counter-proof: Multiplication and addition are enough to implement neural networks, which could eventually implement logical circuits.