6
$\begingroup$

Paillier Homomorphic encryption supports addition and multiplication with plaintext value.

Can I use these properties to calculate the means of cipher-text values? I try to use the following steps:

  1. Multiply set of cipher texts (to get there sum in plaintext value)

  2. Raise the calculated ciphertext in step1 to the power of $\dfrac{1}{c}$ where $c$ is the number of cipher texts) to get the average

The problem I have is that, paillier is defined in integer domain $\mathbb{Z}$ thus $\dfrac{1}{c}$ is always $0$ so the final results is also $0$.

Any help or suggestion?

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of crypto.stackexchange.com/questions/2076/…. Is there anything about your question that is not answered there? $\endgroup$ – mikeazo Nov 18 '17 at 13:25
  • $\begingroup$ To get the "usual" meaning of average, you'd need floating / fixed point arithmetic and no standard crypto primitive has a homomorphism for them. $\endgroup$ – SEJPM Nov 18 '17 at 15:57
  • $\begingroup$ Thank you for replay. I try to use the same basic idea as in PulpSpy's answer in crypto.stackexchange.com/questions/2076/… but the main challenge I have how to raise the double $b^-1$ to power of bigInteger $ciphertext$ when I calculate $E(a)^b^-1$ in java $\endgroup$ – Karen Nov 18 '17 at 18:00
  • $\begingroup$ Is your question just how to do it in Java? If so, that is off-topic for this site. $\endgroup$ – mikeazo Nov 18 '17 at 18:29
  • $\begingroup$ the focus on how to allow mean calculation over the paillier cipher texts. Any suggestion need to be practical (could implement in java). $\endgroup$ – Karen Nov 18 '17 at 18:32
6
$\begingroup$

The Paillier encryption of an integer $x_i$ is given by $c_i = (1+x_iN)r_i^N \bmod N^2$ for some random $0<r_i<N$. Given the encryption of $x_1, \dots, x_k$, the encrypted mean is defined as $$[\![\mu]\!] = \left(\prod_{i=1}^k c_i\right)^{k^{-1}\bmod N} r^N\bmod N^2$$ for some random $0<r<N$.

If we now apply Paillier decryption procedure to $[\![\mu]\!]$, we get $$\mu = \frac{\sum_{i=1}^k x_i}{k} \bmod N$$ We assume $\sum_{i=1}^k x_i< \sqrt{N}$. Now an application of Lagrange-Gauss lattice-reduction algorithm yields $\mu$ as an element in $\mathbb{Q}$.

Based on: [FSW02] Pierre-Alain Fouque, Jacques Stern, and Jan-Geert Wackers. Cryptocomputing with rationals. In Financial Cryptography, volume 2357 of Lecture Notes in Computer Science, pages 136–146. Springer, 2002.


Alternatively, instead of using Lagrange-Gauss algorithm, we can adapt the extended Euclidean algorithm:

 [u1, u2] = [0, N]; [v1, v2] = [1, mu];
 while (u2 > sqrt(N)) do
   Q = u2 div v2; [t1, t2] = [u1, u2] - [v1, v2]*Q;
   [u1, u2] = [v1, v2]; [v1, v2] = [t1, t2];
 endwhile

 return u2/u1

Here is a toy example with $p = 739$, $q = 839$, and $N = pq = 620021$. Suppose $x_1 = 97$, $x_2 = 74$ and $x_3 = 46$.

We are given their respective encryptions: $c_1 = 206197787317$, $c_2 = 267770082390$, and $c_3 = 49804921902$. We have $k=3$ and $k^{-1} \bmod N = 206674$. We choose a random $r<N$, say $r = 559196$ and compute $$[\![ \mu]\!] = (c_1c_2c_3)^{k^{-1}\bmod N} \, r^N \bmod N^2 = 127639014845$$

The decryption of $[\![\mu]\!]$ yields $\mu = 206746 \pmod N$. Lagrange-Gauss algorithm then yields $206746 \equiv \frac{217}3 \pmod N$ and thus $\mu = 217/3 = 72.33$.

$\endgroup$
3
$\begingroup$

The problem I have is that, paillier is defined in integer domain $\mathbb Z$ thus $\frac1c$ is always 0 so the final results is also 0.

You are trying to use real-valued arithmetic here. You are in the wrong field for that. If you are using Paillier Encryption you work in $\mathbb Z_n^*$. The basic operations addition, subtraction, multiplication and division work differently there.

You can compute eg $\operatorname{Enc}(\frac{a+b}2)$ given $\operatorname{Enc}(a)$ and $\operatorname{Enc}(b)$, but this is not $\operatorname{Enc}(2.5)$ for $a=2,b=3$, it is the arithmetic average using the operations for $\mathbb Z_n$, ie the operations that work with a reduction $\bmod n$ after each operation and where division by $a$ works by finding $x$ such that $ax\equiv 1\bmod n$ and then multiplying by $x$.

$\endgroup$
  • $\begingroup$ I hope this clears the main confusion, if anything is left unclear, ask! $\endgroup$ – SEJPM Nov 18 '17 at 21:22
  • 1
    $\begingroup$ To emphesize the point that SEJPM was making, you could compute $\operatorname{Enc}(\frac{a+b}2)$, however, the $/2$ part doesn't mean what you expect; if $a=0$ and $b=1$, then $\operatorname{Enc}(\frac{a+b}2) = \operatorname{Enc}((n+1)/2)$, which is probably not what you're looking for... $\endgroup$ – poncho Nov 18 '17 at 22:10

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.