1
$\begingroup$

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 = L\left(\prod\limits_{j \in S} c_{j}^{2\mu_{0,j}^{S}} \mod n^{2}\right) \times \frac{1}{4\mu^{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}^{2\mu_{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?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.