5 ms·

To 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 ago
Oh. 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 ago
  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.
  - SilasX 6y ago
    The 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 ago
      I think the Wikipedia page is oversimplifying somewhat at the cost of accuracy.
      - SilasX 6y ago
        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-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, "
        ketzu 6y ago
        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.
        anticensor 6y ago
        In GF(2), addition is xor and multiplication is and.
        ketzu 6y ago
        Ah I am way too confused these days, thanks for the correction :)
      - ketzu 6y ago
        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/ https://crypto.stanford.edu/craig/
        heavenlyblue 6y ago
        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.
    - forty 6y ago
      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 :)
    - 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... )
    - baby 6y ago
      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.
EE84M3i 6y ago
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 https://www.gwern.net/Turing-complete
R0b0t1 6y ago
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.

SilasX 6y ago

Oh. 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 ago
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.
- SilasX 6y ago
  The 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 ago
    I think the Wikipedia page is oversimplifying somewhat at the cost of accuracy.
    - SilasX 6y ago
      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-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, "
      - ketzu 6y ago
        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.
        anticensor 6y ago
        In GF(2), addition is xor and multiplication is and.
        ketzu 6y ago
        Ah I am way too confused these days, thanks for the correction :)
    - ketzu 6y ago
      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/ https://crypto.stanford.edu/craig/
      - heavenlyblue 6y ago
        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.
  - forty 6y ago
    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 :)
  - 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... )
  - baby 6y ago
    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.

EE84M3i 6y ago

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 https://www.gwern.net/Turing-complete

R0b0t1 6y ago

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.