2 ms·

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.

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.