Open AndreiEn opened 7 years ago
You should look at Lagrangian interpolation. You can build a polynomial for any function which gives the same value. In mod-p this polynomial will be of degree p, thus big and costly to evaluate homomorphically.
Le 8 juin 2017 5:40 PM, "AndreiEn" notifications@github.com a écrit :
Hello! Let's say i have a and b encrypted mod some p (diffrent than 2, let's say 257). For a comparison between them, I saw in one of your comments that one should make c=a-b, and then to evaluate a mod p polynomial that return 1 if c>0 and 0 otherwise. I don't really understand what did you mean by that, can you give more details ?. Or in other words, how can i evaluate if a ciphertext is greater than 0 (without encrypting the values bit by bit) ?. Or some idea to evaluate |c| - the absolute value of a-b ?
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/shaih/HElib/issues/144, or mute the thread https://github.com/notifications/unsubscribe-auth/AGJNlgyDCiJNK3dvRosItkjdxbZswcSoks5sCBX0gaJpZM4N0QUq .
I looked into Lagrangian interpolation, but it won't work, because my number is either positive or negative. So let's say we get a value of -2 but we also can get 2, and for both cases it should return 2. And from what I understood from Lagrangian interpolation will give a wrong polynomial. Am i wrong ?
You should encode negative numbers into Z mod-p. For example 0..p/2-1 are positive numbers from 0 to p/2-1 and p/2..p-1 are negative numbers -p/2..-1. The interpolated polynomial should return the same value for inputs between 0..p/2-1 and input minus p/2 otherwise. Something like this.
Le 10 juin 2017 6:16 PM, "AndreiEn" notifications@github.com a écrit :
I looked into Lagrangian interpolation, but it won't work, because my number is either positive or negative. So let's say we get a value of -2 but we also can get 2, and for both cases it should return 2. And from what I understood from Lagrangian interpolation will give a wrong polynomial. Am i wrong ?
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/shaih/HElib/issues/144#issuecomment-307574801, or mute the thread https://github.com/notifications/unsubscribe-auth/AGJNlt0U1UVn71HgjT9-MVxMih9bm8HCks5sCsFHgaJpZM4N0QUq .
You are right. Thx a lot. I still have one more question. This idea should work... but like you said it is too costly to evaluate it homomorphic (for more than 5-10 numbers). So what if i just decrypt the difference between the 2 numbers, and i use the value in clear for further computations. Would there be any major threat to security? Because I don't think there is any way to find the two values which produced that difference.
If one number is random it will be secure (it's like one-time pad ciphering). Other cases depend on how the two numbers are obtained.
Hello! Let's say i have a and b encrypted mod some p (diffrent than 2, let's say 257). For a comparison between them, I saw in one of your comments that one should make c=a-b, and then to evaluate a mod p polynomial that return 1 if c>0 and 0 otherwise. I don't really understand what did you mean by that, can you give more details ?. Or in other words, how can i evaluate if a ciphertext is greater than 0 (without encrypting the values bit by bit) ?. Or some idea to evaluate |c| - the absolute value of a-b ?