Hacker News Reader

Comment by giomasce | Hacker News Reader

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?

View on HN

Imagine 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.

Totally 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.

This 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?

But 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".

As far as I can tell it is possible to homomorphically compute a UTM. Since it's possible for a homomorphic circuit to decrypt and reencrypt its own ciphertexts as part of the bootstrapping principle it should also be possible for a circuit to fully decrypt certain values (outputs). Basically, if V = E_K(V') is the homomorphic ciphertext of V' under the primary key, K, and O is an output key, the primary circuit can compute V* = E_O(D_K(V)). An output circuit D_O(X) decrypts values encrypted with the output key, e.g. V' = D_O(V*).

A UTM is an unbounded tape T of encrypted bits, an encrypted state S, a circuit U(S, B) = (S', B', V') representing the state machine of the TM with V' as an output to control the next step, and the circuit for D_O(X). After each evaluation of U the state S is replaced by S', the bit at the current position on the tape is replaced with B', and if V = D_O(V') is 0, move the position on the tape left, if it's 1 move right, and if it's 2 then halt.

A bounded-length Turing Machine can be represented as a finite state machine (with the computing power of a standard physical computer) without leaking any information about changes to the tape by (T', S', V') = FSM(T, S) where the entire tape T is replaced by the output of the circuit at each step and D_O(V') is 1 for continue or 0 for halt.

This depends on your exact definition of an FHE computation. You could imagine a definition under which you can consider the whole scheme a single Turing complete FHE. But this definition would have to accept that the FHE computation is unbounded and leaks computation length (as would any Turing complete scheme).

I don't like the name "termination oracle", it sound too much like "halting oracle" which is not what is going on here. All we do is add an outer while-loop, a simple algorithmic transformation. I wouldn't even consider that an oracle.

After 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).

No, 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.

Seems 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.

ketzu isn't claiming that one can always describe a Turing machine using addition and multiplication only, only that one can describe a Turing machine's map on bounded inputs using addition and multiplication on the input only.

And that's precisely what I challenged. You can't even describe a Turing machine on one single input (using whatever operations you like) if you're not able to determine if that machine is going to terminate. And in general you are not (at least, I am not; if you are, I happen to have a few Turing machines for which I'd be happy to pay to know if they're going to terminate or not; good money, I promise).

You hold a misconception.

The task is not that; instead we assume that we already have a table that correctly describes the TM's maps from bounded input to output when they terminate. His claim is that this table can be expressed as a function in addition and multiplication with the input as operands. To be more precise, with the input and constant numbers (arbitrarily choosable while designing the description of the function) as operands.

Incidentally,

> You can't even describe a Turing machine on one single input (using whatever operations you like)

is false, we can simply encode it as the encoded tuple of the TM and the input; this is a standard construct when we talk about simulating TMs with a UTM.

> The task is not that; instead we assume that we already have a table that correctly describes the TM's maps from bounded input to output when they terminate. His claim is that this table can be expressed as a function in addition and multiplication with the input as operands.

Ok, if the task is this then everything is very easy, I agree. I was commenting on a much harder task, i.e., converting a generic TM to a function adding and multiplying the inputs. That is something you can't do.

> is false, we can simply encode it as the encoded tuple of the TM and the input; this is a standard construct when we talk about simulating TMs with a UTM.

I don't see how that disproves my assertion. I was saying something different, which has to do with your (correct) first assertion: a TM cannot establish if another TM is going to terminate on a certain input.

> I was saying something different

It's important to be precise with language; said encoding is a description of a given TM on a particular input, since a map exists from it to the space of outputs union DOESNOTTERMINATE. Now, whether or not this map is a computable function is a different question.

Alan Turing proved that a solution to the halting problem cannot exist. Per Wikipedia:[0]

> A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines.

It cannot be possible to “map” a Turing machine with a finite number of operations. Without true decision trees and loops, FHE isn’t Turing complete. At minimum, there needs to be a concept of a conditional jump—if X, jump to instruction Y.

You can unravel some programs into a finite set of instructions, but that doesn’t make FHE Turing complete.

Take the following code, for example:

    function f(x):
      while x == 1:
        do nothing
      return x

For a machine to be Turing complete, it must be able to run that function. FHE can’t do that, by definition; it would reveal information about the input.

[0]: https://en.wikipedia.org/wiki/Halting_problem

You can simulate that program you gave on a finite circuit because you can simulate it on your computer which is a finite circuit.

Your computer has circuitry that is capable of being reused. It isn’t a simulator; it could, in theory, run that loop ad infinitum.

FHE can’t reuse circuitry. There’s no concept of, “based on the output, we now need to plug it back in and repeat.” Instead, it has to literally repeat that circuitry for every possible loop.

You could re-run FHE until some condition fails. This is what your CPU does BTW.

Again - the only reason you shouldn’t do that in homomorphic encryption is because this way you will leak run duration information.

You can’t do that—that reveals timing information.

Would you say that this circuit was fully homomorphic if, for all inputs, the processor appeared to be doing the same work?

That is to say? If X = 1 or X = 2 the processor did not appear to “do nothing” but, instead, performed an operation on an encrypted string that was constant time?

I’m not really sure what you’re asking. By definition, FHE cannot be Turing complete. A Turing machine must be capable of performing operations that cannot be handled in constant time, and for which the timing reveals information about the input. That is a fundamental feature of Turing machines; it’s the whole basis for how they came about.

Why can't FHE be capable of performing unbounded operations?

There’s no way to do a FHE style system with branching unless all branches are indistinguishable from one another. All branches must execute in the same amount of time, otherwise statistical analysis will leak information.

Forget Turing completeness for a second, that’s not actually what you want for a FHE style system. You want computational indistinguishability which can’t be achieved without side-channel resistance.

Some of the original work around FHE implies the researchers were applying ML models. If you had a complicated enough ML model (e.g. of a person) you could simulate a computer in that model. The assertion that FHE with just multiplication and addition is Turing-complete is true, and this is one proof.

If you can think of something besides encoding a Turning machine's state as NN weights I am very interested. Perhaps encoding a quantum circuit somehow? A technically correct but intractable solution would be simulating the quantum state of every atom in a silicon circuit.

in 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.

The 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.

You 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.

You 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.

If 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.

I 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.

I am not saying there are not practical ways to do useful computation with this stuff. I am commenting on the theoretical remark that any algorithm (as in any Turing machine) can be executed with FHE, which is false, as it can be proved that it is impossible to compute, given an abstract Turing machine, an upper bound on the length of its execution.

This is generally solved by unrolling the program into a single loop. Essentially having a function state(N) => state(N+1), shouldContinue.

This exposes the number of iterations needed to finish the computation. That could further be limited by underlying code rounding the iterations to mask the real count.

TLDR: either the run time is fixed or you leak some info via the run time.

I believe that's not the issue: the remote machine which performs the calculations on the encrypted data is TM complete and can perform unbounded loops. Comparison is the puzzler for me too: e.g., how do you take min(a, b) if you don't know how a and b compare? We know that F(a) + F(b) = F(a + b), so the remote machine can use "normal" addition operations, but still a > b and F(a) < F(b) can both be true, so it can't use "normal" comparisons, unless there's some implication of the properties of FHE I didn't see.

In theory we could compute the full table of values of a function like less(x: F, y: F) -> {0, 1}, interpolate a bivariate polynomial containing all those values, and build a circuit to evaluate that polynomial. Its degree would be around 2|F| though, so it would be completely impractical.

In SNARK programming, we would usually decompose field elements into bits, then apply a binary comparison circuit. Binary decomposition can be done non-determinstically, by having the prover give the purported bits as "advice" inputs, then having the circuit accumulate those bits and check the sum.

I haven't done any FHE circuit programming, but I imagine that approach wouldn't work, since the circuit must be deterministic. I imagine any values that might need to be compared would just be encoded as binary from the start. (Or is there a better approach?)

Interesting idea, but then it's not TM complete, since the problem space is by definition finite, isn't it? So it seems to me the importance of comparison for TM-completeness is still unsolved.

Then again, it just occurred to me that perhaps fully homomorphic implies that F(0) = 0 and F(1) = 1, so a > b could become F(a - b) ρ 0, and you only need to determine beforehand if ρ is > or <.

Couldn’t the results indicate the need to re-run a circuit? While f(x) x=g(x) would simply return f(x)||g(x).

Okay but that example is just one conditional branching. Turing-completeness requires that you be able to e.g. keep looping back until some condition is met.

If you want to build arbitrary functions like you've described, it reduces to the question of whether you can "unroll" the function, given its inputs[1], into a (stateless) circuit. But that would still IIUIC just get you primitive recursive functions (i.e. those where you can know the upper bound on the number of loop iterations for any loop before it starts), not the general recursive functions you need for Turing-completeness.

Anyone know how you pull off general recursive functions from just addition and multiplication?

[1] and in FHE you don't know the inputs either, which is another kink.

> that would still IIUIC just get you primitive recursive functions (i.e. those where you can know the upper bound on the number of loop iterations for any loop before it starts)

The primitive recursive functions cannot be expressed using circuits. Circuits by definition can only express polynomials, which have a much smaller growth rate than what primitive recursive functions are capable of.

[edit]

Actually, probably a better reason is that in primitive recursion, the running time can depend on the input. For a circuit, the running time is independent of the input.

The circuit that repeatedly multiplies the previous result with itself has higher than exponential growth rate.

No, because you can only multiply a fixed number of times.

Good luck finding something that grows faster than https://en.wikipedia.org/wiki/Ackermann_function

Easy, just square it. Also, the Ackermann function is not a primitive recursive function.

FHE is just a math equation. Can you accept the requirement that you process the state more than once? If so you could do something like encode the atomic state of a silicon circuit somehow and step it forward in time.

That is probably what the researcher is referring to. You can encapsulate computation, but not in a single math equation.

To summarise the other comments: No, it's not actually Turing complete. The programs you can express using circuits have a fixed running time.

Oh. But FHE means Turing-complete, right? So what else do they have besides addition and multiplication that allows them to do arbitrary computations?

FHE 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.

The definition of FHE specifies arbitrary computation:

https://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_H...

If it's really just addition and multiplication, it's not FHE.

I think the Wikipedia page is oversimplifying somewhat at the cost of accuracy.

Weird, 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-...

[2] "Since all mathematical and logical operations can be built from additive and multiplicative operations, "

Regarding [2]: Xor and And form a basis of all logical operations, while Xor on its own (or And on its own) do not. In GF(2) multiplication is xor and addition is and. So addition and multiplication are enought to build all possible circuits.

Another way to look at it is, in homomorphic encryption you have the problem that in an operation both operands are encrypted. Therefore repeated addition based on one operand is not an option.

In GF(2), addition is xor and multiplication is and.

Ah I am way too confused these days, thanks for the correction :)

Actually, Gentrys thesis abstract says this [1]:

> Such a scheme allows one to compute arbitrary functions over encrypted data without the decryption key [- i.e. ...]

My understanding is, while FHE can not implement an algorithm to solve a problem of arbitrary size input, it can apply arbitrary computations to a limited size input.

[1] https://crypto.stanford.edu/craig/

But neither your computer can if you bound your PC to always take the same amount of time to execute any problem you give it.

The issue with such a system that would allow arbitrary computation is that it would certainly allow to extract the value, which mean it would be simpler not to encrypt it in the first place :)

Arbitrary computation can still be bounded. [1] for example cites the definition of FHE (Def. 9) as a scheme that can compute all circuits, which are fairly powerful [2].

Arbitrary computation is also, afaik, not well defined.

edit: After putting some thought into this, I feel like the idea is: Circuits can perform arbitrary computations on a limited size input, but not on an arbitrary size input. 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.

[1] https://eprint.iacr.org/2015/1192.pdf

[2] https://en.wikipedia.org/wiki/Circuit_complexity

>Arbitrary computation is also, afaik, not well defined.

Yes it is, it's Turing-completeness.

> Yes it is, it's Turing-completeness.

While this may be a sensible interpretation, and I am willing to believe it's used in that interpretation in some fields, I have a hard time actually finding a definition of that form.

I also have a problem with using it in this way: In circuits the size of the circuit limits your input size. But given a maximum size of the input, and no size limitations on the circuit, you can construct a circuit that produces the same result as a turing machine that halts. So you can compute whatever you want (i.e. arbitrary) but you are limited by the size of your current circuit.

(Completely unhelpful but always fun to look at for words: https://books.google.com/ngrams/graph?content=arbitrary+comp... )

As gone over in the discussion above [1], you can only compute those TMs that you can unroll into a fixed size circuit, which means (at most) only the subset of TMs that halt; doing this in the general case requires a halting oracle, which is not possible. That's not arbitrary computation by any reasonable definition.

Furthermore, it adds a huge constraint to programming: you can only implement loops with iterations bounded by a constant known at compile time. (And if you derive any of those constants from the inputs at the time you're compiling it for the FHE machine to execute, you've leaked information about said inputs.)

[1] https://news.ycombinator.com/item?id=24019212

My computer is not Turing complete, yet it can do arbitrary computations.

FHE is bounded-memory Turing complete, the same as every computer on the planet.

See my cousin comment [1]: your computer does not require that you be able to determine whether your programs halt and then unroll them into a fixed-size stateless circuit, so that's a big difference.

[1] https://news.ycombinator.com/item?id=24022339

There are two solutions for this. 1) The halting problem is decidable (but untractable) for bounded machines. 2) Instead of deciding when to halt inside the machine, do it outside with continuations. Encrypted computing will always enforce time-limits thus this is not an issue.

With addition and multiplication you can do a lot. I think there is a term for circuits that can be “arithmetized”. A loop which iteration count is based on the value of the encrypted input seems to be out of scope.

Part of what's going on here is conflicting definitions of what "Turing complete" means in a formal context and how it's often used among practitioners.

A specific circuit has a fixed running time, but it can do arbitrary computations in that runtime, including emulating a fixed number of steps of an arbitrary Turing machine.

Our physical computers also have limitations (particularly space) on what Turing machines they can simulate, however they are often called "Turing complete" in general parlance. Obviously a laptop though has limitations that are on completely different orders of magnitude though, and are much more efficient.

Many "surprisingly Turing complete"[1] systems have similar limitations, but the more interesting question is "can you use this system to simulate a bounded number of steps of a Universal Turing machine?" and the answer for those systems, and FHE is yes.

[1]: https://www.gwern.net/Turing-complete

Like a physics simulation you iterate the cryptographic math over time. The physical laws themselves are incapable of expressing computation, it is the effect they have on a system evolving over time that produces what we call computation.

Comparisons 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.

Yes, 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.

There 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

Sure, 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.

If 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 :)

That's my point: not any Turing machine can be implemented with FHE, because FHE must have bounded execution time.

You can either say “a Turing machine can not be implemented” or “it can” but never “not any Turing machine” because there isn’t any types of a Turing machine - just a single one.

You don’t need to branch, you execute both branches at the same time.

You 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

Quick counter-proof: Multiplication and addition are enough to implement neural networks, which could eventually implement logical circuits.

Code might finaly look like with movfuscator (MOV on a intel processor is also turing complete).

No, it can't. FHE cannot emulate the whole MOV, especially the features that make it Turing-complete.

The 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.

Movfuscator 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.

True, but there are simpler (abstract) machines that also achieve Turing completeness: 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)

What does "functionally complete" means for you?

Informally, 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).

You get bounded-Turing completeness. This is sufficient for all practical applications as we live in a finite universe.

Personal 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.

Any 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

I 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.

Reply on news.ycombinator.com