5
$\begingroup$

Can we make subtraction result of cipher texts encrypted by Pascal Paillier absolute. Just like we use method Math.abs() in Java ? For example, if we subtract 0 from 1: 1-0 = 1, it is positive but 0-1 = -1. My requirement is that this subtraction should always be positive like:

   1 - 0 = 1
   0 - 1 = 1

Is there anyway i can achieve it please?

$\endgroup$
  • $\begingroup$ Technically, $-1$ is equivalent to a positive number in the Paillier group, but I am assuming that is not what you are looking for. $\endgroup$ – mikeazo Nov 2 '15 at 18:13
  • $\begingroup$ @mikeazo you mean if i perform this operation: (1-0) + (0-1) + (1-0) then output will be 3 instead of 1 ? $\endgroup$ – Umer Nov 3 '15 at 6:46
  • $\begingroup$ No, you would get 1. $\endgroup$ – mikeazo Nov 3 '15 at 13:04
  • $\begingroup$ yes. But I want to get 3. $\endgroup$ – Umer Nov 3 '15 at 16:23
  • $\begingroup$ If you know when to expect a negative number, you can multiply by -1, otherwise it is impossible. $\endgroup$ – mikeazo Nov 3 '15 at 16:41
6
$\begingroup$

No, or at least, if you can, you have an Extremely Significant result; you've just shown that Paillier is a Fully Homomorphic system, and so it could perform any operation on encrypted data (and in a way that's significantly more efficient than any other known FHE system).

Here's why: The $|a - b|$ operation is effectively an $XOR$; if the ciphertexts $a, b$ are known to be either encrypted $0$ or $1$ values, then the result will be a 1 if they differ, and 0 if they are the same.

In addition with a bit more work, we can compute an $AND$. To do this, we could first compute $a + b - |a - b|$. This value will be an encrypted 2 if $a, b$ are both 1, and 0 if either is a 0. Then, multiplying this value by the constant $(n+1)/2$ (which can be done in $O(\log n)$ homomorphic additions) will give us an encrypted 1 if both $a, b$ are 1, 0 otherwise (or, on other words, an $AND$ operation).

The combination of the $AND$ and $XOR$ operations are complete; that is, any function (computable in bounded time) can be implemented by a sufficient number of them.

We don't believe that Paillier is an FHE system, hence either what you're asking for is infeasible, or we have a really exciting result on our hands.

| improve this answer | |
$\endgroup$
  • $\begingroup$ A good explanation of XOR and AND operation but it went out of scope of my question. I know Pailier encryption is not FHE, My question is that, can we we compute absolute value or not ? And I think you have replied that in the very first word which is No. $\endgroup$ – Umer Nov 3 '15 at 6:55
  • $\begingroup$ @Umer, poncho said no, unless Paillier is FHE, because addition and abs implies FHE. As we do not believe that Paillier is FHE, the answer is very likely no. So the whole answer is a very good explanation. $\endgroup$ – mikeazo Nov 3 '15 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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