4
$\begingroup$

Paillier has additive homomorphic property that states:

  1. if two ciphers c1 and c2, are multiplied, and the result is decrypted, it is equal to addition of the two plaintexts.

D(c1*c2)= m1+m2

  1. Paillier also allows two ciphers to be added. If the addition result is decrypted, we get the addition of the two plaintexts also.

D(c1+c2) = m1+m2

The two operations lead to the same result i.e., m1+m2.

However the second operation is only mentioned in Paillier python libraries and not in the formal definition of Paillier.

What is the difference between the two and if both are valid, is it true that Paillier has many-to-one homomorphic property.

The second property is mentioned in the python library pdf as follows:

Once this party has received some EncryptedNumber instances (e.g. see Serialisation), it can perform basic mathematical operations supported by the Paillier encryption:

  1. Addition of an EncryptedNumber to a scalar
  2. Addition of two EncryptedNumber instances
  3. Multiplication of an EncryptedNumber by a scalar
$\endgroup$
0

1 Answer 1

4
$\begingroup$

In standard Paillier encryption

  • Property 1 really is: $m_1=D(c_1)\text{ and }m_2=D(c_2)\implies D(c_1\cdot c_2\bmod n^2) = m_1+m_2\bmod n$.
  • Property 2 does not hold (but see final off-topic note).

As a consequence of property 1, for all $k$ in $\mathbb Z$, it holds $D({c_1}^k\bmod n^2)\ =\ m_1\cdot k\bmod n$. Proof for positive $k$ can be by induction, proof for negative $k$ follows from group properties of multiplication in $\mathbb Z_{n^2}^*$ and $\mathbb Z_n^*$.

Note: For integers $u$, $v$ and $w$, by definition of $u\bmod v=w$, that means $u-w$ is a multiple of $v$ and $0\le w<v$. The operator $\bmod$ has priority less than $+$ (thus less than $\cdot$) but more than $=$. Contrast with operator % in computer languages, which typically has priority more than +.


Once this party has received some EncryptedNumber instances (e.g. see Serialisation), it can perform basic mathematical operations supported by the Paillier encryption:

  1. Addition of an EncryptedNumber to a scalar
  2. Addition of two EncryptedNumber instances
  3. Multiplication of an EncryptedNumber by a scalar

That's correct if we take addition and multiplication modulo $n$. Given $c_1$ and $c_2$ such that $m_1=D(c_1)$ and $m_2=D(c_2)$, and a scalar $k$ in $\mathbb Z$, any party knowing the public key $(n,g)$ can

  1. Compute $c$ such that $D(c)=m_1+k\bmod n$, by encrypting $k$ and applying property 1. That is $c\gets c_1\cdot g^k\cdot r^n\bmod n^2$ for some $r$ coprime with $n$ (possibly $r=1$ if hiding $k$ and that $c$ derives from $c_1$ are pointless in the application).

  2. Compute $c$ such that $D(c)=m_1+m_2\bmod n$, by application of property 1.

  3. Compute $c$ such that $D(c)=m_1\cdot k\bmod n$, by application of the consequence of property 1.


The doc linked in the question is for a library that adds a wrapper on Paillier encryption. This is the part of the source doing the crypto. The library handles negatives and floating point numbers, as explained there, by

  • Restricting it's plaintext integers to range $\left[\,-\left\lfloor n/3\right\rfloor,\left\lfloor n/3\right\rfloor\,\right]$, with negatives mapped to $\left[\,n-\left\lfloor n/3\right\rfloor,n-1\,\right]$ of standard Paillier encryption.
  • Separating mantissa (encrypted with sign as above) and exponent (which remains in clear).

Off-topic: Python allows operator + to perform anything the programmer wants when applied to objects defined by the programmer. Both in the above library and the simpler code linked in comment, + for two ciphertexts has been coerced overloaded to call an internal function that makes use of property 1, thus performs a multiplication modulo $n^2$. Similarly, * has been overloaded to call an internal function that makes use of the consequence of property 1, thus performs an exponentiation modulo $n^2$.

$\endgroup$
3
  • $\begingroup$ Can you check this library: pypi.org/project/paillierlib It says: m1 = mpz(10) m2 = mpz(1) c1 = paillier.encrypt(m1, key_pair.public_key) c2 = paillier.encrypt(m2, key_pair.public_key) # Example homomorphic operations # Addition paillier.decrypt(c1 + c2, key_pair.private_key) # => 11 paillier.decrypt(c1 - c2, key_pair.private_key) # => 9 paillier.decrypt(c1 + c1 + c2, key_pair.private_key) # => 21 $\endgroup$
    – Mimi
    Apr 17, 2021 at 4:50
  • $\begingroup$ yes the source you mentioned is the correct one. $\endgroup$
    – Mimi
    Apr 17, 2021 at 10:30
  • 1
    $\begingroup$ @Tasneem Ghunaim: your question turns out to be a programming one (thus off-topic), specifically about operator overloading, as explained in the answer's last paragraph. I expanded the butlast paragraph about what the pyphe library does. $\endgroup$
    – fgrieu
    Apr 17, 2021 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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