3 ms·
FHE means you hide the input and processed output from the processor, not the operation. From the abstract, it's talking about hiding the operation [1]. IOW,
by SilasX 13y ago
FHE means you hide the input and processed output from the processor, not the operation. From the abstract, it's talking about hiding the operation [1].
IOW, FHE means: "I know I added your numbers, but I don't know what they are or what their sum is. Here's the encrypted sum."
[1] First sentence: Informally, an obfuscator O is an (efficient, probabilistic) “compiler” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is “unintelligible” in some sense.
- darkmighty 13y agoActually, FHE can hide the operation. Since it can execute arbitrary non-linear operations, one that it can do is "Do a step in this encrypted Turing machine". What Black box obfuscation demands which is impossible is "Take this plaintext, do a step in an obfuscated Turing machine and return me the plaintext solution", i.e. there's no obfuscation which makes it "hard" to determine the operations for arbitrary Turing machines/circuits given plaintext I/O.
- SilasX 13y ago>Actually, FHE can hide the operation. Since it can execute arbitrary non-linear operations, one that it can do is "Do a step in this encrypted Turing machine". Do you have a source on that? Because it sounds suspect. FHE works by constructing a (malleability-exploiting) circuit to implement the desired logic on the (malleable) ciphertext. So it seems it would have to decrypt the relevant step in that Turing machine to build the circuit.
- swordswinger12 13y agoThe details are more complicated, but he/she might be talking about http://eprint.iacr.org/2013/229.pdf http://eprint.iacr.org/2013/229.pdf
- SilasX 13y agoSince you understand the paper well enough to vouch for the claim, could you spell out how you can encrypt operations like that in a way that doesn't contradict the "no obfuscation" paper (or otherwise show the latter wrong)?
- sillysaurus3 13y ago(This is exactly the question I've been trying to ask throughout this thread. Thank you for asking it directly. Hopefully someone here knows the answer, but it's looking more and more to be a mystery that will require some new effort to solve.)
- darkmighty 13y agoThe no obfuscation paper requires plaintext input, FHE requires encrypted input. What's unclear here? There's no contradiction: If you have the plaintext input, you are required to have at least a (non garbled) function describing your operation, so it doesn't imply obfuscation. Anything that can be written as a function can exploit FHE, as long as the output doesn't grow (i.e. you have to account for growth before)
- sillysaurus3 13y agoWhere in the no-obfuscation paper does it say it requires plaintext input? Searching for the word "plaintext" only reveals three results, and all of them are talking about a chosen plaintext attack. The paper doesn't seem to specify any requirements about the input.
- SilasX 13y agoAnd as I asked of swordswinger, since you seem to have a good enough understanding of this to vouch for it, could you summarize how you implement a FHE operation without knowing what the operation ("plainfunction") is?
- 13y ago
- deleted 13y ago[deleted]
- wyager 13y ago>FHE works by constructing a (malleability-exploiting) circuit to implement the desired logic on the (malleable) ciphertext. That's a very simplistic view of FHE. There are much more complex homomorphisms that you can take advantage of, that I don't think can be called "malleability". There is a lot of research going into FHE based on ring homomorphisms, because you can e.g. encode any logical operations as addition and multiplication over GF(2). I would not be surprised at all if you could encrypt computations with FHE.