Cryptography
public-key keys homomorphic-encryption paillier
Updated Sat, 21 May 2022 16:01:24 GMT

I'm getting a non-integer (float) private key in Paillier encryption


I'm trying to implement the Paillier cryptosystem in Matlab using the key generation guidance available here: https://en.wikipedia.org/wiki/Paillier_cryptosystem#Key_generation, but the problem is that with any combination of prime numbers I try, I get a float mu required for the private key.

The first step is:

Choose two large prime numbers p and q

Just for a starting point I chose p = 17 and q = 19.

Compute ${\displaystyle n=pq}$ and ${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)} $.

Which I achieved in Matlab using:

n = p*q;
lambda = lcm((p - 1), (q - 1));

This gives me n = 323 and lambda = 144

Third step:

Select random integer ${\displaystyle g}$ where $g\in {\mathbb Z}_{{n^{{2}}}}^{{*}}$

I read that g = n + 1 satisfies all the required conditions so I went with that, which gives me a g = 324.

Fourth step is to compute ${\displaystyle \mu}$ using:

${\displaystyle \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}}$

where, ${\displaystyle L}$ is defined as ${\displaystyle L(x)={\frac {x-1}{n}}} $

I achieved this using:

a = (powermod(g, lambda, n*n) - 1) / n;
gMu = mod(inv(a),n);

So at this stage, the public key is supposed to be (n,g) = (323,324) and the private key would be (lambda,mu) which in my case comes to (144,0.0069).

Why am I getting a float value of gMu whereas all the implementations I have seen online provide a integer value of private keys.

Where am I getting this wrong?




Solution

Looks like you missed the note on wikipedia:

Note that the notation ${\frac {a}{b}}$ does not denote the modular multiplication of $a$ times the modular multiplicative inverse of $b$ but rather the quotient of $a$ divided by $b$, i.e., the largest integer value $v\geq 0$ to satisfy the relation $a\geq vb$.

As a side note, to make key generation even simpler, there is another note on wikipedia you may be interested in:

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







External Links

External links referenced by this document: