Repository files navigation

An implementation of the Paillier cryptosystem relying on the native JS implementation of BigInt.

It can be used by anyWeb Browser or webview supporting BigInt and with Node.js (>=10.4.0). In the latter case, for multi-threaded primality tests, you should use Node.js v11 or newer or enable at runtime withnode --experimental-worker with Node.js version >= 10.5.0 and < 11.

The operations supported on BigInts are not constant time. BigInt can be thereforeunsuitable for use in cryptography. Many platforms provide native support for cryptography, such asWeb Cryptography API orNode.js Crypto.

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.

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

D( E(m₁) · E(m₂) ) mod n² = m₁ + m₂ mod n

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

D( E(m₁) · g^m₂ ) mod n² = m₁ + m₂ mod n

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

D( E(m₁)^m₂ mod n² ) = m₁ · m₂ mod n,

D( E(m₂)^m₁ mod n² ) = m₁ · m₂ mod n.

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

D( E(m₁)^k mod n² ) = k · m₁ mod n.

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

1. Define the bit length of the modulusn, orkeyLength in bits.
2. Choose two large prime numbersp andq randomly and independently of each other such thatgcd( p·q, (p-1)(q-1) )=1 andn=p·q has a key length of keyLength. For instance:
   1. Generate a random primep with a bit length ofkeyLength/2 + 1.
   2. Generate a random primeq with a bit length ofkeyLength/2.
   3. Repeat until the bitlength ofn=p·q iskeyLength.
3. Compute parametersλ,g andμ. Among other ways, it can be done as follows:
   1. Standard approach:
      1. Computeλ = lcm(p-1, q-1) withlcm(a, b) = a·b / gcd(a, b).
      2. Generate randomsα andβ inZ* ofn, and select generatorg inZ* ofn**2 asg = ( α·n + 1 ) β**n mod n**2.
      3. Computeμ = ( L( g^λ mod n**2 ) )**(-1) mod n whereL(x)=(x-1)/n.
   2. If using p,q of equivalent length, a simpler variant would be:
      1. λ = (p-1, q-1)
      2. g = n+1
      3. μ = λ**(-1) mod n

Thepublic (encryption)key is(n, g).

Theprivate (decryption)key is(λ, μ).

Letm in[0, n) be the clear-text message,

1. Select random integerr inZ* ofn.

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

Letc be the ciphertext to decrypt, wherec in(0, n**2).

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

paillier-bigint can be imported to your project withnpm:

npm install paillier-bigint

Then either require (Node.js CJS):

constpaillierBigint=require('paillier-bigint')

or import (JavaScript ES module):

import*aspaillierBigintfrom'paillier-bigint'

The appropriate version for browser or node is automatically exported.

You can also download theIIFE bundle, theESM bundle or theUMD bundle and manually add it to your project, or, if you have already importedpaillier-bigint to your project, just get the bundles fromnode_modules/paillier-bigint/dist/bundles/.

An example of usage could be:

asyncfunctionpaillierTest(){// (asynchronous) creation of a random private, public key pair for the Paillier cryptosystemconst{ publicKey, privateKey}=awaitpaillierBigint.generateRandomKeys(3072)// Optionally, you can create your public/private keys from known parameters// const publicKey = new paillierBigint.PublicKey(n, g)// const privateKey = new paillierBigint.PrivateKey(lambda, mu, publicKey)constm1=12345678901234567890nconstm2=5n// encryption/decryptionconstc1=publicKey.encrypt(m1)console.log(privateKey.decrypt(c1))// 12345678901234567890n// homomorphic addition of two ciphertexts (encrypted numbers)constc2=publicKey.encrypt(m2)constencryptedSum=publicKey.addition(c1,c2)console.log(privateKey.decrypt(encryptedSum))// m1 + m2 = 12345678901234567895n// multiplication by kconstk=10nconstencryptedMul=publicKey.multiply(c1,k)console.log(privateKey.decrypt(encryptedMul))// k · m1 = 123456789012345678900n}paillierTest()

Consider usingbigint-conversion if you need to convert from/to bigint to/from unicode text, hex, buffer.

Check the API