A node.js implementation of the Paillier cryptosystem

This is a node.js implementation relying on the node-bignum library by Stephan Thomas. Bignum is an arbitrary precision integral arithmetic for Node.js using OpenSSL. For a pure javascript implementation that can be used on browsers, please visit paillier-bigint.

The Paillier cryptosystem, named after and invented by Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. A notable feature of the Paillier cryptosystem is its homomorphic properties.

Homomorphic properties

Homomorphic addition of plaintexts

The product of two ciphertexts will decrypt to the sum of their corresponding plaintexts,

D( E(m1) · E(m2) ) mod n^2 = m1 + m2 mod n

The product of a ciphertext with a plaintext raising g will decrypt to the sum of the corresponding plaintexts,

D( E(m1) · g^(m2) ) mod n^2 = m1 + m2 mod n

(pseudo-)homomorphic multiplication of plaintexts

An encrypted plaintext raised to the power of another plaintext will decrypt to the product of the two plaintexts,

D( E(m1)^(m2) mod n^2 ) = m1 · m2 mod n,

D( E(m2)^(m1) mod n^2 ) = m1 · m2 mod n.

More generally, an encrypted plaintext raised to a constant k will decrypt to the product of the plaintext and the constant,

D( E(m1)^k mod n^2 ) = k · m1 mod n.

However, given the Paillier encryptions of two messages there is no known way to compute an encryption of the product of these messages without knowing the private key.

Key generation

1. Define the bit length of the modulus n, or keyLength in bits.
2. Choose two large prime numbers p and q randomly and independently of each other such that gcd( p·q, (p-1)(q-1) )=1 and n=p·q has a key length of keyLength. For instance:
   1. Generate a random prime p with a bit length of keyLength/2 + 1.
   2. Generate a random prime q with a bit length of keyLength/2.
   3. Repeat until the bitlength of n=p·q is keyLength.
3. Compute λ = lcm(p-1, q-1) with lcm(a, b) = a·b / gcd(a, b).
4. Select a generator g in Z* of n^2. g can be computed as follows (there are other ways):
   • Generate randoms α and β in Z* of n.
   • Compute g=( α·n + 1 ) β^n mod n^2.
5. Compute μ=( L( g^λ mod n^2 ) )^(-1) mod n where L(x)=(x-1)/n.

The public (encryption) key is (n, g).

The private (decryption) key is (λ, μ).

Encryption

Let m in Z* of n be the clear-text message,

1. Select random integer r in (1, n^2).

2. Compute ciphertext as: c = g^m · r^n mod n^2

Decryption

Let c be the ciphertext to decrypt, where c in (0, n^2).

1. Compute the plaintext message as: m = L( c^λ mod n^2 ) · μ mod n

Usage

Every input number should be a string in base 10, an integer, or a BigNum. All the output numbers are instances of BigNum.

// import paillier
const paillier = require('paillier.js');

// synchronous creation of a random private, public key pair for the Paillier cyrptosystem
const {publicKey, privateKey} = paillier.generateRandomKeys(3072);

// asynchronous creation of a random private, public key pair for the Paillier cyrptosystem (ONLY from async function)
const {publicKey, privateKey} = await paillier.generateRandomKeysAsync(3072);

// optionally, you can create your public/private keys from known parameters
const publicKey = new paillier.PublicKey(n, g);
const privateKey = new paillier.PrivateKey(lambda, mu, p, q, publicKey);

// encrypt m
let c = publicKey.encrypt(m);

// decrypt c
let d = privateKey.decrypt(c);

// homomorphic addition of two chipertexts (encrypted numbers)
let c1 = publicKey.encrypt(m1);
let c2 = publicKey.encrypt(m2);
let encryptedSum = publicKey.addition(c1, c2);
let sum = privateKey.decrypt(encryptedSum); // m1 + m2

// multiplication by k
let c1 = publicKey.encrypt(m1);
let encryptedMul = publicKey.multiply(c1, k);
let mul = privateKey.decrypt(encryptedMul); // k · m1

See usage examples in example.js.

Classes

Functions

Typedefs

PaillierPublicKey

Class for a Paillier public key

Kind: global class

• PaillierPublicKey
  • new PaillierPublicKey(n, g)
  • .bitLength ⇒ number
  • .encrypt(m) ⇒ bignum
  • .addition(...ciphertexts) ⇒ bignum
  • .multiply(c, k) ⇒ bignum

new PaillierPublicKey(n, g)

Creates an instance of class PaillierPublicKey

| Param | Type | Description | | --- | --- | --- | | n | bignum | string | number | the public modulo | | g | bignum | string | number | the public generator |

paillierPublicKey.bitLength ⇒ number

Get the bit length of the public modulo

Kind: instance property of PaillierPublicKey
Returns: number - - bit length of the public modulo

paillierPublicKey.encrypt(m) ⇒ bignum

Paillier public-key encryption

Kind: instance method of PaillierPublicKey
Returns: bignum - - the encryption of m with this public key

| Param | Type | Description | | --- | --- | --- | | m | bignum | string | number | a cleartext number |

paillierPublicKey.addition(...ciphertexts) ⇒ bignum

Homomorphic addition

Kind: instance method of PaillierPublicKey
Returns: bignum - - the encryption of (m_1 + ... + m_2) with this public key

| Param | Type | Description | | --- | --- | --- | | ...ciphertexts | bignums | 2 or more (big) numbers (m_1,..., m_n) encrypted with this public key |

paillierPublicKey.multiply(c, k) ⇒ bignum

Pseudo-homomorphic paillier multiplication

Kind: instance method of PaillierPublicKey
Returns: bignum - - the ecnryption of k·m with this public key

| Param | Type | Description | | --- | --- | --- | | c | bignum | a number m encrypted with this public key | | k | bignum | string | number | either a cleartext message (number) or a scalar |

PaillierPrivateKey

Class for Paillier private keys.

Kind: global class

• PaillierPrivateKey
  • new PaillierPrivateKey(lambda, mu, publicKey, [p], [q])
  • .bitLength ⇒ number
  • .n ⇒ bignum
  • .decrypt(c) ⇒ bignum

new PaillierPrivateKey(lambda, mu, publicKey, [p], [q])

Creates an instance of class PaillierPrivateKey

| Param | Type | Default | Description | | --- | --- | --- | --- | | lambda | bignum | string | number | | | | mu | bignum | string | number | | | | publicKey | PaillierPublicKey | | | | [p] | bignum | string | number | | a big prime | | [q] | bignum | string | number | | a big prime |

paillierPrivateKey.bitLength ⇒ number

Get the bit length of the public modulo

Kind: instance property of PaillierPrivateKey
Returns: number - - bit length of the public modulo

paillierPrivateKey.n ⇒ bignum

Get the public modulo n=p·q

Kind: instance property of PaillierPrivateKey
Returns: bignum - - the public modulo n=p·q

paillierPrivateKey.decrypt(c) ⇒ bignum

Paillier private-key decryption

Kind: instance method of PaillierPrivateKey
Returns: bignum - - the decryption of c with this private key

| Param | Type | Description | | --- | --- | --- | | c | bignum | string | a (big) number encrypted with the public key |

generateRandomKeys(bitLength, simplevariant) ⇒ KeyPair

Generates a pair private, public key for the Paillier cryptosystem in synchronous mode

Kind: global function
Returns: KeyPair - - a pair of public, private keys

| Param | Type | Default | Description | | --- | --- | --- | --- | | bitLength | number | 4096 | the bit lenght of the public modulo | | simplevariant | boolean | false | use the simple variant to compute the generator |

generateRandomKeysAsync(bitLength, simplevariant) ⇒ Promise.<KeyPair>

Generates a pair private, public key for the Paillier cryptosystem in asynchronous mode

Kind: global function
Returns: Promise.<KeyPair> - - a promise that returns a KeyPair if resolve

| Param | Type | Default | Description | | --- | --- | --- | --- | | bitLength | number | 4096 | the bit lenght of the public modulo | | simplevariant | boolean | false | use the simple variant to compute the generator |

KeyPair : Object

Kind: global typedef
Properties

| Name | Type | Description | | --- | --- | --- | | publicKey | PaillierPublicKey | a Paillier's public key | | privateKey | PaillierPrivateKey | the associated Paillier's private key |