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 n2 = 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) · gm2 ) mod n2 = 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 n2 ) = m1 · m2 mod n,
D( E(m2)m1 mod n2 ) = 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 n2 ) = 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
- Define the bit length of the modulus
n
, or keyLength
in bits. - 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:
- Generate a random prime
p
with a bit length of keyLength/2 + 1
. - Generate a random prime
q
with a bit length of keyLength/2
. - Repeat until the bitlength of
n=p·q
is keyLength
.
- Compute parameters
λ
, g
and μ
. Among other ways, it can be done as follows:
- Standard approach:
- Compute
λ = lcm(p-1, q-1)
with lcm(a, b) = a·b / gcd(a, b)
. - Generate randoms
α
and β
in Z*
of n
, and select generator g
in Z*
of n**2
as g = ( α·n + 1 ) β**n mod n**2
. - Compute
μ = ( L( g^λ mod n**2 ) )**(-1) mod n
where L(x)=(x-1)/n
.
- If using p,q of equivalent length, a simpler variant would be:
λ = (p-1, q-1)
g = n+1
μ = λ**(-1) mod n
The public (encryption) key is (n, g).
The private (decryption) key is (λ, μ).
Encryption
Let m
in [0, n)
be the clear-text message,
-
Select random integer r
in Z*
of n
.
-
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)
.
- 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')
...
- JavaScript native or TypeScript project (including Angular and React)
import * as paillierBigint from 'paillier-bigint'
...
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'
...
</script>
- JavaScript native browser IIFE
<head>
...
<script src="../../lib/index.browser.bundle.iife.js"></script>
</head>
<body>
...
<script>
...
</script>
</body>
Then you could use, for instance, the following code:
async function paillierTest () {
const { publicKey, privateKey } = await paillierBigint.generateRandomKeys(3072)
const m1 = 12345678901234567890n
const m2 = 5n
const c1 = publicKey.encrypt(m1)
console.log(privateKey.decrypt(c1))
const c2 = publicKey.encrypt(m2)
const encryptedSum = publicKey.addition(c1, c2)
console.log(privateKey.decrypt(encryptedSum))
const k = 10n
const encryptedMul = publicKey.multiply(c1, k)
console.log(privateKey.decrypt(encryptedMul))
}
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
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 | Default | 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
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 |