# How to compute Lambda in a Threshold Paillier scheme

I am evaluating a threshold Paillier scheme as described in the paper:

Ivan Damgard, Mads Jurik, Jesper Buus Nielsen, "A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting", 2010, Aarhus University, Dept. of Computer Science, BRICS.

and have a problem with evaluating ${\lambda_{0,i}^S}$ in the share combining step.

In the paper, ${\lambda_{0,i}^S}$ is computed as:

${\lambda_{0,i}^S} = \Delta \displaystyle \prod_{i^{'} \in S \setminus i} \frac{-i}{i - i'}$.

for S secret shares.

The same way of computing ${\lambda_{0,i}^S}$ is mentioned in another paper about threshold Paillier scheme:

Ivan Damgard, Mads Jurik, "A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system.", 2001, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography Springer-Verlag.

Unfortunately, the value of ${\lambda_{0,i}^S}$ described as above does not let me to combine shares properly.

There is a Paillier Threshold Encryption Toolbox which computes ${\lambda_{0,i}^S}$ in another way:

${\lambda_{0,i}^S} = \Delta \displaystyle \prod_{i^{'} \in S \setminus i} \frac{-i'}{i - i'}$.

and I can confirm this version works as expected. These two approaches give completely different values. For instance, having 3 decryption servers we have:

With the first approach:

${\lambda_{0,1}^S} = 3$, ${\lambda_{0,2}^S} = -24$, ${\lambda_{0,3}^S} = 27$

With the second approach:

${\lambda_{0,1}^S} = 18$, ${\lambda_{0,2}^S} = -18$, ${\lambda_{0,3}^S} = 6$

There is a chance it's just a typo in the paper but I find it quite unlikely. On the other hand, trying two approaches on a simple example proves that the second approach gives correct decryption and the first approach (original from paper) does not.

What is the correct way of computing ${\lambda_{0,i}^S}$ parameter for combining shares in a threshold Paillier scheme? What am I missing here?

### <Enc,Dec> roundtrip sample:

Let's have $p = 5$, $q = 7$, $p' = 2$ and $q' = 3$.

They satisfy $p = 2p' + 1$ and $q = 2q' + 1$.

$n = pq = 35$, $m = p'q' = 6$.

Number of decryption servers is $l = 3$ and threshold is $w = 3$.

I pick $d = 36$ such that $d \equiv 0 (mod \: m)$ and $d \equiv 1 (mod \: n)$

Hiding polynomial is expressed as:

$f(X) = {\displaystyle\sum_{i=0}^{w-1}} a_i X^i$

where

$a_0 = d$

$a_i$ for $0<i<w$ is a random value from $[0, nm)$

Picking random $a_1$ and $a_2$, let's make it

$f(X) = 36 + 7x + 116x^2$

Secret shares are:

$s_1 = f(1) = 159$

$s_2 = f(2) = 94$

$s_3 = f(3) = 51$

Let's encrypt $M=29$.

Encrypted text $c$ is:

$c=(n+1)^M r^n \: mod \: n^2$

where $r$ is a randomly chosen $r \in Z_n$. Let's use $r = 19$ which gives us:

$c = (35 + 1)^{29} \ast 19^{35} \: mod \: 35^2 = 234$

Now, since we have our secret we can try to decrypt it. We first need to do share decryption for each decryption server $i$:

$c_i = c^{2 \Delta s_i}$

where $\Delta = l!$ (factorial of total number of decryption servers) and $s_i$ is a previously evaluated secret share for server $i$

We have 3 encryption servers, so $\Delta = 3! = 6$.

Shares are then combined into $c'$ in the following way:

$c' = \Delta \displaystyle \prod_{i \in S} c_i^{2 \lambda_{0,i}^S} \: mod \: n^2$

where ${\lambda_{0,i}^S}$ is computed with one of the previously discussed approaches.

I'll use a small trick here.

Since $A^B \: mod \: C = (A \: mod \: C)^B \: mod \: C$

and $(AB) \: mod \: C = (A \: mod \: C \ast B \: mod \: C) \: mod \: C$

We can include $mod$ operation for each decrypted share to avoid creating large numbers. This way:

$c_1 = 234^{2 \ast 6 \ast 159} \: mod \: n^2 = 1121$

$c_2 = 234^{2 \ast 6 \ast 94} \: mod \: n^2 = 771$

$c_3 = 234^{2 \ast 6 \ast 51} \: mod \: n^2 = 106$

When we use the approach from paper:

${\lambda_{0,i}^S} = \Delta \displaystyle \prod_{i^{'} \in S \setminus i} \frac{-i}{i - i'}$.

${\lambda_{0,1}^S} = 3$, ${\lambda_{0,2}^S} = -24$, ${\lambda_{0,3}^S} = 27$

$c' = 1156$

When we use the other approach:

${\lambda_{0,1}^S} = 18$, ${\lambda_{0,2}^S} = -18$, ${\lambda_{0,3}^S} = 6$

${\lambda_{0,i}^S} = \Delta \displaystyle \prod_{i^{'} \in S \setminus i} \frac{-i'}{i - i'}$.

$c' = 386$

(I did not find this information anywhere, but I assume we must do $abs(\lambda)$ to avoid creating fractions for negative values like $-18$ or $-24$.

If we decrypt the message with:

$M = 4 \Delta^2 \frac{c' - 1}{N} \: mod^{-1} N$

since

$c' = (1+N)^{4 \Delta^2 M}$

we'll get:

$M = 17$ for $c' = 1156$ which is wrong.

and

$M = 29$ for $c' = 386$ which is correct.

• seems similar to lagrange's interpolation, which shamir's secret sharing is based on? – Husen May 30 '18 at 9:22

Unfortunately, it is a typo in the original paper.

In the key generation step, the private key $d$ is split into $l$ shares using $(w,l)$-Shamir secret sharing, i.e. the key is split into $l$ shares and reconstructing the key needs $w$ shares.

Essentially, a degree $w-1$ random polynomial is generated by choosing $w-1$ random coefficient $a_{w-1},\ldots,a_1$ and set $d$ as the free coefficient: $$f(x) = a_{w-1}x^{w-1}+a_{w-2}x^{w-2}+\cdots+a_1x+d$$ then each share $s_i=f(i)$ for $1\le i\le l$

Noting that $d$ is essentially $f(0)$ that can be computed from the shares using Lagrange interpolation. Let's say now $w$ authorities want to decrypt, and in total they have $w$ out of the $l$ shares. Let $S$ be a set of the indexes of those shares, then:

$$f(0) = {\sum_{i\in S}} s_i \cdot \lambda_i(0)$$

where

$$\lambda_i(0) =\prod_{m\in S\setminus i} \frac{0- x_m}{x_i-x_m}$$

Also noting that when generating the shares the indexes were used as $x$ values, i.e. $x_m=m$, so

$$\lambda_i(0) =\prod_{m\in S\setminus i} \frac{0- m}{i-m}$$

If you substitute $m$ with $i'$, you will get

$$\lambda_i(0) =\prod_{i'\in S\setminus i} \frac{- i'}{i-i'}$$

which is essentially in the other formula that gives you the correct result ($\lambda_{0,i}^S=\Delta\cdot \lambda_{i}(0)$).

The decryption is done by computing:

$$c'=\prod_{i\in S} c_i^{2\lambda_{0,i}^S}=\prod_{i\in S} c^{2\Delta s_i\cdot2\lambda_{0,i}^S}=\prod_{i\in S} c^{4\Delta^2 s_i\lambda_i(0)}= c^{4\Delta^2{\sum_{i\in S}} s_i \cdot \lambda_i(0)}=c^{4\Delta^2d}$$

As you can see, the private key $d$ is reconstructed in the exponent.

• What should I do with the negative value of ${\lambda}$ ? Is that correct to always take an absolute value? For example, for 3 parties, ${\lambda_{0,2}^S} = -18$ used in the exponent gives a fraction. – omnomnom Jun 1 '18 at 16:52
• $c^{-18}=(c^{-1})^{18}$, where $c^{-1}$ is the multiplicative inverse modulo $n^2$. The inverse is an integer, see en.wikipedia.org/wiki/Modular_multiplicative_inverse – Changyu Dong Jun 2 '18 at 12:12