Mental Models 4 Life

The Paillier Cryptosystem is a partial homomorphic encryption scheme that supports two important operations: addition of two encrypted integers and the multiplication of an encrypted integer by an unencrypted integer. In practice, many applications of Paillier require an extension of the underlying scheme beyond integers to handle floating-point numbers. For example, just about every popular machine learning algorithm require floating-point numbers.

Unfortunately, most open-source implementations of Paillier only deal with non-negative integers. In this post, I show how Paillier can be extended to handle floating-point numbers, starting from the homomorpheR package. I decided to write this post because there doesn’t appear to be a single accessible article that deals with all the different aspects of the extension in one place. I claim no novelty here, however; all the important ideas come from the Python implementation of Paillier by N1 Analytics and other online discussions.

The homomorpheR package comes with several primitives that are shown in the following code snippet.

library(homomorpheR)
keypair = PaillierKeyPair$new(modulusBits = 1024)
pubkey = keypair$pubkey
privkey = keypair$getPrivateKey()
privkey$decrypt(pubkey$add(pubkey$encrypt(5), pubkey$mult(pubkey$encrypt(6),5)))

The Paillier primitives from homomorpheR are defined only on positive integers. We approximate a floating point number X by 3 integers (a,b,c) such that X is approximately equal to for a suitable largenum.

For example, assuming largenum = 2^10, the number 5.2 can be represented by (5, 204, 0) = (5 + 204/1024) / 1 = 5.19922, or  (50, 2040, 1) = (50 + 2040/1024) / 10 = 5.19922. In general, the larger largenum is, the better the approximation is.

The above considerations lead to the following function for encoding floating-point numbers. (The function works on integers also, of course.)

largenum = 2^50
encodeFloat = function(x, e=0) {
    x = x * 10^e
    x1 = floor(x)
    x2 = x - x1
    x2 = floor(x2 * largenum)
    exps = rep(e, length(x))
    zipf(x1,x2,exps)
}

# Convenience function
zipf = function(x1,x2,x3) {
    res = c()
    for (i in 1:length(x1)) res = c(res,x1[i],x2[i],x3[i])
    res
}

We encrypt each number (a,b,c) by encrypting a and b with the public key. The input to the following function can be a vector of numbers.

zero = pubkey$encrypt('0')
encrypt = function(z, e=0) {
    y = encodeFloat(z, e)
    res = rep(zero, length(y))
    for (i in 1:length(y)) {
        if (i %% 3 == 0) { res[i] = y[i] }
        else { res[i] = pubkey$encrypt(as.character(y[i])) }
    }
    res
}

We decrypt each encrypted number (enc(a), enc(b),c) using the private key by computing . The input to the following function can be a vector of numbers. We deal with negative numbers as suggested here.

decrypt = function(en) {
    uen = en
    for (i in 1:length(uen)) {
        if (i %% 3 != 0) uen[i] = privkey$decrypt(en[i])
    }
    # deal with negative results
    for (i in 1:length(uen)) {
        if (i %% 3 != 0 && # don't process exponents
            uen[i] >= as.double(pubkey$n/3.0)) { uen[i] = uen[i] - pubkey$n }
    }
    res = c()
    for (i in seq(1, length(uen), 3)) {
        res = c(res,
               (as.double(uen[i]) + as.double(uen[i+1]/(largenum))) / as.double(10^uen[i+2]))
    }
    return(res)
}

We next define addition of two encrypted numbers: (enc(a1), enc(b1), c1) and (enc(a2), enc(b2), c2). Addition can be done on the encrypted a’s and encrypted b’s if c1 = c2. We make c1 = c2 true by multiplying by powers of 10 when necessary.The need to make c1 = c2 is the reason why we can’t have c1 and c2 encrypted. The below function works on vectors of numbers.

addenc = function(x, y) {
    res = x
    for (i in seq(1, length(x), 3)) {
        if (x[i+2] != y[i+2]) { # if different exponent, make the exponents equal by multiplying
            res[i+2] = max(x[i+2], y[i+2])
            xdiff = res[i+2] - x[i+2]
            ydiff = res[i+2] - y[i+2]
            if (xdiff > 0) {
                x[i] = pubkey$mult(x[i], 10^(xdiff))
                x[i+1] = pubkey$mult(x[i+1], 10^(xdiff))
            }
            if (ydiff > 0) {
                y[i] = pubkey$mult(y[i], 10^(ydiff))
                y[i+1] = pubkey$mult(y[i+1], 10^(ydiff))
            }
        }
        res[i] = pubkey$add(x[i], y[i])
        res[i+1] = pubkey$add(x[i+1], y[i+1])
    }
    res
}

We next define subtraction of two encrypted numbers: (enc(a1), enc(b1), c1) and (enc(a2), enc(b2), c2). We simply multiply the second encrypted number by -1 and then add it to the first encrypted number.

subenc = function(x, y) {
    for (i in seq(1, length(x), 3)) {
        y[i] = pubkey$mult(y[i], -1)
        y[i+1] = pubkey$mult(y[i+1], -1)
    }
    addenc(x, y)
}

Finally, we define the multiplication of an encrypted number en = (enc(a),enc(b),c) by a scalar y. Again, Paillier only allows y to be an integer. To deal with floating point numbers, we use

, where n is a parameter with larger n leading to better approximation. We use n = 5 below.

smultenc = function(x,y) {
    prec = 5
    yint = floor(y * 10^prec)
    res = x
    for (i in seq(1, length(x), 3)) {
        res[i] = pubkey$mult(x[i], yint)
        res[i+1] = pubkey$mult(x[i+1], yint)
        res[i+2] = x[i+2] + prec
    }
    res
}

Here are some test cases

# five = encrypt(5.4)
# ten = encrypt(10.2)
# hundred = encrypt(100.75)
# negseven = encrypt(-7.6)
# five
# ten
# decrypt(negseven)
# decrypt(addenc(five,ten))
# decrypt(subenc(ten,five))
# decrypt(subenc(five,ten))
# decrypt(addenc(c(five,ten), c(ten,ten)))
#
# five = encrypt(5.4,1)
# ten = encrypt(10.2,2)
# decrypt(addenc(five,ten))
# decrypt(subenc(ten,five))
# decrypt(addenc(c(five,ten), c(ten,ten)))
#
# decrypt(smultenc(five, 4))
# decrypt(smultenc(ten, 6))
# decrypt(smultenc(c(five,ten), 4))
# decrypt(smultenc(c(five,ten), -4))

# five = encrypt(5.4)
# ten = encrypt(10.2)
# hundred = encrypt(100.75)
# negseven = encrypt(-7.6)

# 5.4 + 100.75 * 5.9 - (-7.6) + 10.2
# decrypt(addenc(ten, subenc(addenc(five, smultenc(hundred, 5.9)), negseven)))

Now you’re ready to do some real work with Paillier!