3
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – omnomnom Jun 1 '18 at 16:52
  • 1
    $\begingroup$ $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 $\endgroup$ – Changyu Dong Jun 2 '18 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.