# Combining share decryption on Paillier threshold scheme

I am trying to implement the Paillier threshold scheme described by Fouque, et al, but I am having an issue when combining share decryptions.

The scheme calculates the plaintext $$M$$ with the formula:

$$M = Lleft(prodlimits_{j in S} c_{j}^{2mu_{0,j}^{S}} mod n^{2}right) times frac{1}{4mu^{2}theta} mod n$$

Where $$mu_{0,j}^{S} = Delta times prod_{j’ in S setminus {j}} frac{j’}{j’ – j} in mathbb{Z}$$

For a list of shares $$S$$, where on code it is represented by a list of objects $$(id: i, value: c_i)$$ where $$i$$ is the share ID and $$c_i$$ the value, I am trying calculate $$mu_{0,j}^{S}$$ with the following pseudocode Python code:

``````def combine(shares: Set[Decryption], key, params) -> int:
n = key.n
n_squared = n * n

threshold, Δ = params.threshold, params.Δ
c = 1

shares = shares[:threshold]
for i in shares:
µ = Δ

for j in shares:
print(i.id, j.id)
if i is j:
continue

µ *= j.id // (j.id - i.id)
c *= pow(i.value, 2 * µ, n_squared)

L = 4 * Δ * Δ
c //= L * key.θ
return ((c - 1) // n * modular_inverse(L, n)) % n
``````

The problem is when I get to the second iteration, where `i.id` is 2, and the inner for starts with `j.id` as 1. Thus, $$mu$$ is negative when I calculate $$frac{j’}{j’ – j}$$ because $$j’$$ (`j.id`) is smaller than $$j$$ (`i.id`), then $$j’ – j$$ becomes negative.

The effect is that $$mu$$ is negative (every other iteration yields positive factors to multiply), so $$c_{j}^{2mu_{0,j}^{S}}$$ elevates $$c_j$$ to a negative exponent.

Did I miss something from the paper, or is it working as expected and I have to handle this negative exponent some other way?

#### Combining share decryption on Paillier threshold scheme

Shopping cart
There are no products in the cart!
Continue shopping
0