3
$\begingroup$

In the context of Fully Homomorphic Schemes, we use a technique called "bootstrapping" to refresh the ciphertext, by evaluating homomorphically the decryption circuit with an encrypted version of the private key.

I was wondering if it was possible to consider this approach, of reducing the error size, by using an error-control code instead (eventually designed for our FHE scheme).

I am not concerned about the efficiency of such a scheme right now, but would it be feasible to design a scheme such that we can apply an "error-reducing code" reducing errors instead of correcting all of them. I don't think there have been researches to this idea so far so it is maybe completely unthinkable but I wanted to discuss it with other people..

Improve this question
$\endgroup$
4
  • $\begingroup$ Interesting question, The error we talked in FHE is due to semantic security. The bootstrapping, while decrypting the ciphertext encrypts again, semantically. I don't want to dismiss totally to discourage you, but it would be impossible due to the semantic security. $\endgroup$
    – kelalaka
    Commented Nov 27, 2018 at 9:18
  • $\begingroup$ But my point here is what if we get rid of this notion of bootstrapping by introducing rather this idea of error reduction via error-control codes. Especially I've seen some homomorphic schemes based on certain families of linear codes. Wouldn't it be feasible, at least in theory in this context? $\endgroup$
    – Binou
    Commented Nov 28, 2018 at 9:57
  • $\begingroup$ And could you explain this part "it would be impossible due to the semantic security" ? Because error-correcting codes correct some random errors appearing, so I don't really understand your point $\endgroup$
    – Binou
    Commented Nov 29, 2018 at 5:34
  • $\begingroup$ It's a natural idea indeed, but I never heard of anyone getting to get it to work. Good luck ;) $\endgroup$
    – LeoDucas
    Commented Jul 5, 2019 at 19:39

1 Answer 1

Reset to default
-1
$\begingroup$

I think not, because the two types of error correction are doing fundamentally different things.

Conventional error correction schemes, for instance Reed-Solomon codes, expect the value to be near some codeword. To correct an erroneous value, they change it to the nearest codeword. You can picture it as a space where some points in the space correspond to correct values, and each of those points is encircled by a region of incorrect values that belong to that point. The assumption of error correction is that value started at a correct point and drifted a little, but stayed in the point's own region.

With LWE, you are mixing the correct value with a ton of error, and secretly you know some way to unmix it later (bootstrapping). You can't use less error and still have security. In terms of the point analogy above, the incorrect values have to be all over the space. They can't stay close to their correct value in any obvious way. Otherwise anybody could see what the correct value is - it's the nearest correct point. I doubt that you can use any conventional error correction without having obvious regions of some kind.

Error correction doesn't do much for the bootstrapping either, I think, because once you unmix the value, you can just throw away the error part.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.