paillier-bigint

paillier-bigint

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

It can be used by any Web 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 with node --experimental-worker with Node.js version >= 10.5.0 and < 11.

The operations supported on BigInts are not constant time. BigInt can be therefore unsuitable for use in cryptography. Many platforms provide native support for cryptography, such as Web Cryptography API or Node.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.

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

Installation

paillier-bigint can be imported to your project with npm:

npm install paillier-bigint

NPM installation defaults to the ES6 module for browsers and the CJS one for Node.js. For web browsers, you can also directly download the IIFE bundle or the ESM bundle from the repository.

Usage

Import your module as :

• Node.js

  const paillierBigint = require('paillier-bigint')
  ... // your code here
  

• JavaScript native or TypeScript project (including Angular and React)

  import * as paillierBigint from 'paillier-bigint'
  ... // your code here
  

  Notice that paillier-bigint relies on bigint-crypto-utils which cannot be polyfilled to suport older browsers. If you are using webpack/babel to create your production bundles, you should target only the most modern browsers. For instance, for React apps created with create-react-app, you should edit your package.json and modify the browserList so that it only targets the latest browsers (supporting the latest features):

  "browserslist": {
    "production": [
      "last 1 chrome version",
      "last 1 firefox version",
      "last 1 safari version"
    ],
    "development": [
      "last 1 chrome version",
      "last 1 firefox version",
      "last 1 safari version"
    ]
  }
  

  Also, notice that BigInt is ES-2020. In order to use it with TypeScript you should set lib (and probably also target and module) to esnext in tsconfig.json.
• JavaScript native browser ES module

  <script type="module">
     import * as paillierBigint from 'lib/index.browser.bundle.mod.js'  // Use you actual path to the broser mod bundle
     ... // your code here
   </script>
  

• JavaScript native browser IIFE

  <head>
    ...
    <script src="../../lib/index.browser.bundle.js"></script> <!-- Use you actual path to the browser bundle -->
  </head>
  <body>
    ...
    <script>
      ... // your code here
    </script>
  </body>
  

Then you could use, for instance, the following code:

async function paillierTest () {
  // (asynchronous) creation of a random private, public key pair for the Paillier cryptosystem
  const { publicKey, privateKey } = await paillierBigint.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)

  const m1 = 12345678901234567890n
  const m2 = 5n

  // encryption/decryption
  const c1 = publicKey.encrypt(m1)
  console.log(privateKey.decrypt(c1)) // 12345678901234567890n

  // homomorphic addition of two ciphertexts (encrypted numbers)
  const c2 = publicKey.encrypt(m2)
  const encryptedSum = publicKey.addition(c1, c2)
  console.log(privateKey.decrypt(encryptedSum)) // m1 + m2 = 12345678901234567895n

  // multiplication by k
  const k = 10n
  const encryptedMul = publicKey.multiply(c1, k)
  console.log(privateKey.decrypt(encryptedMul)) // k · m1 = 123456789012345678900n
}
paillierTest()

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

API reference documentation

PublicKey

Class for a Paillier public key

Kind: global class

• PublicKey
  • new PublicKey(n, g)
  • .bitLength ⇒ number
  • .encrypt(m, [r]) ⇒ bigint
  • .addition(...ciphertexts) ⇒ bigint
  • .multiply(c, k) ⇒ bigint

new PublicKey(n, g)

Creates an instance of class PublicKey

Param	Type	Description
n	bigint	the public modulo
g	bigint	the public generator

publicKey.bitLength ⇒ number

Get the bit length of the public modulo

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

publicKey.encrypt(m, [r]) ⇒ bigint

Paillier public-key encryption

Kind: instance method of PublicKey
Returns: bigint - - the encryption of m with this public key

Param	Type	Description
m	bigint	a bigint representation of a cleartext message
[r]	bigint	the random integer factor for encryption. By default is a random in (1,n)

publicKey.addition(...ciphertexts) ⇒ bigint

Homomorphic addition

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

Param	Type	Description
...ciphertexts	bigint	n >= 2 ciphertexts (c_1,..., c_n) that are the encryption of (m_1, ..., m_n) with this public key

publicKey.multiply(c, k) ⇒ bigint

Pseudo-homomorphic Paillier multiplication

Kind: instance method of PublicKey
Returns: bigint - - the encryption of k·m with this public key

Param	Type	Description
c	bigint	a number m encrypted with this public key
k	bigint | number	either a bigint or a number

PrivateKey

Class for Paillier private keys.

Kind: global class

• PrivateKey
  • new PrivateKey(lambda, mu, publicKey, [p], [q])
  • .bitLength ⇒ number
  • .n ⇒ bigint
  • .decrypt(c) ⇒ bigint
  • .getRandomFactor(c) ⇒ bigint

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

Creates an instance of class PrivateKey

Param	Type	Default	Description
lambda	bigint
mu	bigint
publicKey	PublicKey
[p]	bigint		a big prime
[q]	bigint		a big prime

privateKey.bitLength ⇒ number

Get the bit length of the public modulo

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

privateKey.n ⇒ bigint

Get the public modulo n=p·q

Kind: instance property of PrivateKey
Returns: bigint - - the public modulo n=p·q

privateKey.decrypt(c) ⇒ bigint

Paillier private-key decryption

Kind: instance method of PrivateKey
Returns: bigint - - the decryption of c with this private key

Param	Type	Description
c	bigint	a bigint encrypted with the public key

privateKey.getRandomFactor(c) ⇒ bigint

Recover the random factor used for encrypting a message with the complementary public key. The recovery function only works if the public key generator g was using the simple variant g = 1 + n

Kind: instance method of PrivateKey
Returns: bigint - - the random factor (mod n)
Throws:

• RangeError - Cannot recover the random factor if publicKey.g != publicKey.n + 1. You should generate yout keys using the simple variant, e.g. generateRandomKeys(3072, true) )

Param	Type	Description
c	bigint	the encryption using the public of message m with random factor r

generateRandomKeys([bitlength], [simplevariant]) ⇒ Promise.<KeyPair>

Generates a pair private, public key for the Paillier cryptosystem.

Kind: global function
Returns: Promise.<KeyPair> - - a promise that resolves to a KeyPair of public, private keys

Param	Type	Default	Description
[bitlength]	number	3072	the bit length of the public modulo
[simplevariant]	boolean	false	use the simple variant to compute the generator (g=n+1). This is REQUIRED if you want to be able to recover the random integer factor used when encrypting with the public key

generateRandomKeysSync([bitlength], [simplevariant]) ⇒ KeyPair

Generates a pair private, public key for the Paillier cryptosystem in synchronous mode. Synchronous mode is NOT RECOMMENDED since it won't use workers and thus it'll be slower and may freeze thw window in browser's javascript.

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

Param	Type	Default	Description
[bitlength]	number	3072	the bit length of the public modulo
[simplevariant]	boolean	false	use the simple variant to compute the generator (g=n+1)

KeyPair : Object

Kind: global typedef
Properties

Name	Type	Description
publicKey	PublicKey	a Paillier's public key
privateKey	PrivateKey	the associated Paillier's private key