paillier-bignum

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

PaillierPublicKey

Class for a Paillier public key

PaillierPrivateKey

Class for Paillier private keys.

Functions

generateRandomKeys(bitLength, simplevariant) ⇒ KeyPair

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

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

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

Typedefs

KeyPair : Object

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

---