Mental Models 4 Life

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 where is the Paillier encryption function with a public key. To do that, we compute , 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 . We generate two random numbers and and compute and We then send x’ and y’ to the private key holder, who computes and , multiplies the two numbers, and then send back . We can then take z and compute 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!