3 ms·

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 pow

by ketzu 6y ago

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 https://eprint.iacr.org/2015/1192.pdf [2] https://en.wikipedia.org/wiki/Circuit_complexity https://en.wikipedia.org/wiki/Circuit_complexity

SilasX 6y ago
>Arbitrary computation is also, afaik, not well defined. Yes it is, it's Turing-completeness.
- ketzu 6y ago
  > 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+computation%2Cturing+complete&corpus=26&year_start=1800&year_end=2019&smoothing=3&direct_url=t1%3B%2Carbitrary%20computation%3B%2Cc0%3B.t1%3B%2Cturing%20complete%3B%2Cc0#t1%3B%2Carbitrary%20computation%3B%2Cc0%3B.t1%3B%2Cturing%20complete%3B%2Cc0 https://books.google.com/ngrams/graph?content=arbitrary+comp... )
  - SilasX 6y ago
    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 https://news.ycombinator.com/item?id=24019212
- rrobukef 6y ago
  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.
  - SilasX 6y ago
    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 https://news.ycombinator.com/item?id=24022339
    - rrobukef 6y ago
      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.

by ketzu 6y ago

SilasX 6y ago

>Arbitrary computation is also, afaik, not well defined. Yes it is, it's Turing-completeness.

ketzu 6y ago
> 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+computation%2Cturing+complete&corpus=26&year_start=1800&year_end=2019&smoothing=3&direct_url=t1%3B%2Carbitrary%20computation%3B%2Cc0%3B.t1%3B%2Cturing%20complete%3B%2Cc0#t1%3B%2Carbitrary%20computation%3B%2Cc0%3B.t1%3B%2Cturing%20complete%3B%2Cc0 https://books.google.com/ngrams/graph?content=arbitrary+comp... )
- SilasX 6y ago
  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 https://news.ycombinator.com/item?id=24019212
rrobukef 6y ago
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.
- SilasX 6y ago
  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 https://news.ycombinator.com/item?id=24022339
  - rrobukef 6y ago
    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.