Join Log in
Score:0
Paprika avatar Crypto

Extracting/learning info from fully homomorphic schemes

cn flag
Paprika

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?

51
0 + 0
kelalaka avatar
in flag
kelalaka
No, you cannot, to learn you have to decrypt. If you look at the [FHE Circuits](https://crypto.stackexchange.com/q/63781/18298) 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...
0
Reply
kelalaka avatar
in flag
kelalaka
If you can learn without decrypting, aren't you breaking the scheme? **Then what?** What do you want to achieve?
0
Reply
Paprika avatar
cn flag
Paprika
@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?
0
Reply
kelalaka avatar
in flag
kelalaka
Yes, you [encrypt and send the server](https://crypto.stackexchange.com/a/88776/18298) and the server operates and gives you the result in the encrypted form.
0
Reply
kelalaka avatar
in flag
kelalaka
No for AI to learn, the ciphertexts are indistinguishable from random. Cryptography is more ready against AI years ago.
0
Reply
meshcollider avatar
gb flag
meshcollider
There is also an idea of "zero testing", i.e. learning whether an encrypted value is zero or not without learning what it is. This could be useful in some situations (i.e. testing equality by subtraction and zero testing).
0
Reply
knaccc avatar
es flag
knaccc
There is a much simpler solution to your problem. Latitudes are in the range -90 to 90, or to make things simpler, consider it instead to be a number between 0 and 180. Then each client picks a random blinding factor $b$ between 0 and 180, and reports to you their latitudes as $latitude + b$ $mod 180$. Now you can easily observe the latitudinal distance they've travelled, without knowing what their latitudes actually are, or if they are the same latitudes as any other client.
0
Reply
Score:0
avatar Crypto
sa flag
K.G.

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.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.