Multiplication and Comparison Operations in Paillier

As is well known, the Paillier encryption system supports addition of two encrypted numbers and the scalar multiplication of a constant and an encrypted number. I learned recently one can compare two encrypted numbers and multiply two encrypted numbers in Paillier by making a trip to the private key holder.

Let’s first look at comparison. Suppose we want to know, for two arbitrary numbers x and y, whether enc(y) > enc(x), where enc() is the Paillier encryption function with a public key. To do that, we compute (enc(y) - enc(x)) \cdot r, where r is a randomly generated number, and then send it to the private key holder to decrypt and tell us the sign of the number, which depending on application can be returned as an unencrypted boolean value or an encrypted 1 or 0.

Let’s now look at multiplication of two encrypted numbers enc(x) \cdot enc(y). We generate two random numbers r1 and r2 and compute x' = enc(x) \cdot r1 and y' = enc(y) \cdot r2. We then send x’ and y’ to the private key holder, who computes dec(x') and dec(y'), multiplies the two numbers, and then send back z = enc(dec(x') \cdot dec(y')). We can then take z and compute z \cdot \frac{1}{r1\cdot r2} to get what we want. In this way, no party ever knows what the other party want to conceal.

In practice, some care needs to be taken in the selection of the random numbers, especially their ranges. For added security, one can use quantum random number generators like those from Quintessence Labs.

The obvious downside to the above algorithms is the need to consult the private key holder, which can be expensive over a wide-area network. Functional programming techniques like partial evaluation can be used to alleviate the problem, allowing all (partial) computations to be done before an approach to the private key holder is made as a last resort. The use of partial evaluation, interestingly, should provide additional security from the private key holder learning the underlying data too, so win-win!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s