Paillier’s encryption Scheme

The Paillier crypto system, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing \(n-th\) residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.

Key Generation:

  1. Choose two large prime numbers \(P\) and \(Q\) randomly and indenpendently of each other such that \(gcd(PQ, (P-1)(Q-1))=1\). This property is assured if both primes are equal lenth.

[1]:

from klefki.const import (SECP256K1_P as P, SECP256K1_N as Q)

[2]:

from math import gcd

assert gcd(P * Q, (P - 1) * (Q - 1)) == 1

  1. Compute \(N=PQ\) and \(\lambda(N)=lcm(P-1, Q-1)\) be the Carmichael function of N.

[3]:

from klefki.numbers import lcm

[4]:

N = P * Q
Lam = lcm(P - 1, Q - 1)

  1. Select random integer \(\Gamma\) where \(\Gamma \in \mathbf{Z}_{n^2}^*\).

[5]:

from random import randint
from klefki.types.algebra.utils import randfield
from klefki.types.algebra.meta import field

F = field(N, "N")
DF = field(N**2, "N^2")
G = randfield(DF)

  1. Ensure \(n\) devides the order of \(g\) by checking the existence of the following modular multiplicative inverse:

\[\mu = (L(G^{\lambda(N)}\mod N^2))^{-1} \mod \ N\]

Where \(L\) be a function defined over the set \(\{x\in \mathbf{Z}_{N^2}: x=1 \ mod \ N\}\) computed as

\[L(x) = \frac{x-1}{N}\]
[6]:

L = lambda x: (x - 1) // N

The public key is \((N, \Gamma)\) and the secret key is \((\lambda(N))\)

If using p,q of equivalent length, a simpler variant of the above key generation steps would be to set \(g = n + 1 , λ = φ ( n )\), and \(\mu = φ(n)^{-1}\ mod \ n\), where \(φ(n)=(p-1)(q-1)\)

[7]:

print("PrivKey: %s" % Lam)

PrivKey: 2234634654990432849929004166367641021238215826767191291571707378398254532167475902984296517123225539202576657105730699764493290075143829571044458305451072

[8]:

print("PubKey: %s; %s" % (N, G))

PubKey: 13407807929942597099574024998205846127429294960603147749430244270389527193005087002084253735130200377185477318450090306135904455919285040173416176828872431; 77035126901414243466593033818616330970366679968094154722572700152333391747783504498549422681480857084131841310916380433218514709109231164061290704333180832878606535936787048649862356920125008479743359336912545136561115652209816489026998639931414361265240792280633335547102958672135420024259094083644382006236

Encryption:

To Encrypt a message \(M \in Z_N\), select \(R \in_R Z_N^*\) and return \(c=\Gamma^M R^N\ mod \ N^2\).

[9]:

import random
import math
m = random.randint(0, N)
assert 0 <= m < N

r = DF(random.randint(0, N))
assert math.gcd(r.value, N) == 1

[10]:

c = G**m * r**N

[11]:

print("Ciphtertext Text: %s" % c)

Ciphtertext Text: 7016628710028750763220234799772443961517829663536340494877375384716387806068796190029061065289125116984936899123466377581433183611140917487456099941786219495981415910545327007385914304277320973108642790490995523777576032108671309475901939594111754694043435450378428378425126512315421950443099829027922257557

Decryption:

To decrypt a ciphertext \(c \in Z_N\), let \(L\) be a function defined over the set \(\{u\in Z_{N^2}: u=1 \ mod \ N\}\) computed as \(L(u) = \frac{u-1}{N}\). Then the decryption of \(c\) is computed as

\[\frac{L(c^{\lambda(N)}\ mod\ N^2)}{L(\Gamma^{\lambda(N)}\ mod\ N^2)}\ mod\ N\]

The function \(L\) is used to compute \(i\) from \((1+n)^i \mod n^2\)

[12]:

assert F(m) == F(L((c ** Lam).value)) * ~F(L(pow(G, Lam).value))

Homomorphic

\[\begin{split}E(m_i) \in Z_{N^2}\\ m_i \in Z_N\end{split}\]

Homomorphic addition

[13]:

from klefki.crypto.paillier import Paillier
from klefki.const import (SECP256K1_P as P, SECP256K1_N as Q)
from klefki.types.algebra.utils import randfield

[14]:

Pai = Paillier(P, Q)
E = Pai.E
D = Pai.D

Lam = Pai.privkey
N, G = Pai.pubkey

F = field(N, "N")

[15]:

m1, m2 = randfield(F), randfield(F)

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

    \[\begin{split}D(E(m_1, r_1) \circ E(m_2, r_2)) = m_1 + m_2\\\end{split}\]
[16]:

assert D(E(m1) * E(m2)) == D(E(m1)) + D(E(m2)) == m1 + m2

  • The product of a ciphertext with a plaintext raising \(g\) will decrypt to the sum of the corresponding plaintexts.

\[\begin{split}D(E(m_1, r_1)\circ g^{m_2}) = m_1+m_2\\\end{split}\]
[17]:

D(E(m1) * (G ** m2)) == m1 + m2

[17]:

True

Homomorphic multiplication

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

\[\begin{split}D(E(m_1, r_1)^{m_2}) = m_1m_2\\ D(E(m_2, r_2)^{m_1}) = m_1m_2\\\\\end{split}\]
[18]:

D(E(m1)**m2) == m1 * m2 == D(E(m2)**m1)

[18]:

True

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

\[D(E(m, r)^{k}) = km\]
[19]:

k = randfield(F)
m = randfield(F)


D(E(m) ** k) == k * m

[19]:

True

Ref

[ ]: