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:
            if i is j:

            µ *= // ( -
        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 is 2, and the inner for starts with as 1. Thus, $mu$ is negative when I calculate $frac{j’}{j’ – j}$ because $j’$ ( is smaller than $j$ (, 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