2
$\begingroup$

On the BFV fully homomorphic scheme, given a polynomial secret key, we can encrypt polynomial plaintexts and generate polynomial ciphertexts.

So, for example, if we have 2 ciphertexts, we can compare them with the less than function, which is 1 if the left polynomial coefficient is less than or equal to the right one, and 0 otherwise. HOWEVER, the result is also an encrypted polynomial, which when decrypted, gives these 0 and 1 numbers.

The question is: how to extract information? How to learn from encrypted data without decrypting it?

Suppose I want to store encrypted latitudes of clients, and learn if they traveled more than 100km in one day. How would I extract such information? I can certainly calculate the difference between the 2 latitudes, but it would be an encrypted difference. Then what?

Improve this question
$\endgroup$
7
  • $\begingroup$ No, you cannot, to learn you have to decrypt. If you look at the FHE Circuits you can see that one has to use the encrypted information to construct the circuits and finally decrypt. It makes the circuits larger, and nearly impossible to build sorting algorithms like Quicksort. In the end, this is the nice property of the FHE that we wanted... $\endgroup$
    – kelalaka
    Jan 21, 2022 at 8:47
  • $\begingroup$ If you can learn without decrypting, aren't you breaking the scheme? Then what? What do you want to achieve? $\endgroup$
    – kelalaka
    Jan 21, 2022 at 8:48
  • $\begingroup$ @kelalaka indeed, but I've seen machine learning stuff. Is it such that the server learns in encrypted form (which is useless for him) but deliver a learned stuff for the client to decrypt? $\endgroup$
    – Paprika
    Jan 21, 2022 at 11:39
  • $\begingroup$ Yes, you encrypt and send the server and the server operates and gives you the result in the encrypted form. $\endgroup$
    – kelalaka
    Jan 21, 2022 at 11:44
  • $\begingroup$ No for AI to learn, the ciphertexts are indistinguishable from random. Cryptography is more ready against AI years ago. $\endgroup$
    – kelalaka
    Jan 21, 2022 at 16:43

1 Answer 1

Reset to default
1
$\begingroup$

In general, you cannot learn from ciphertexts without decryption, and this is what we want. The ability to extract small amounts of information combined with a general computational ability will typically break confidentiality completely.

What you do depends on exactly what you want to do and what your setting is.

One approach is the one you allude to in the comments, where one party creates encryptions of (presumably) secret data, the other party applies a (presumably) secret circuit to the ciphertexts, so the the first party can decrypt the results. This is why strong notions of circuit privacy exist.

In other settings, there may be a trusted third party that can decrypt.

If it is possible to distribute the decryption operation, we can replace the trusted third party with a collection of parties that are less trusted.

These are general approaches. There would be more specialised approaches for more specialised situations.

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.