# Negative exponents in Shoup's threshold RSA?

I'm trying to implement threshold RSA operations, starting with decryption based on

Peeters, R., Nikova, S., & Preneel, B. (2008). Practical RSA Threshold Decryption for Things That Think. Retrieved from http://www.cosic.esat.kuleuven.be/publications/article-1178.pdf

and running into problems where it seems I would have to raise by a negative exponent. The formula is on page 9:

$$w = \prod_{j\in S} x_j^{\lambda_{0,j}^S}$$

Peeters et al. reference

for definitions, which to me seems to have the same issue. I'll quote Shoup page 212:

Let $\Delta=l!$. For any subset $S$ of $k$ points in $\{0, \ldots, l\}$, and for any $i \in \{0, \ldots, l\} \setminus S$, and $j \in S$, we can define $$\lambda_{i,j}^S = \Delta\frac{\prod_{j^\prime \in S\setminus\{j\} }(i-j^\prime)}{\prod_{j^\prime \in S\setminus\{j\} }(j-j^\prime)} \in \mathbf{Z}$$

(which Shoup defines as equation (2), but I couldn't get the embedded LaTeX to do that)

Shoup uses $\lambda$ on page 214: $$w = x_{i_1}^{2\lambda_{0,i_1}^S} \dots x_{i_k}^{2\lambda_{0,i_k}^S}$$

(where $x_i$ were previously calculated to be in $Q_n$, e.g. the subgroup of squares in $\mathbf{Z}_n^*$, n being the RSA modulus, though I'm a little bit out of my depth as to what consequences this has. In any case, Peeters et al. don't use the subgroup of squares.)

My problem is: $\lambda_{0,j}^S$ is negative quite often. Simple example $l=3, k=2, S=\{1,2\}, \Delta = l! = 6$.

For $j=1$: $\lambda_{0,1}^S = \Delta \frac{ (0-2) }{ (1-2) } = 6 \cdot 2$

For $j=2$: $\lambda_{0,2}^S = \Delta \frac{ (0-1) }{ (2-1) } = 6 \cdot -1$

How am I supposed to use that in an exponent?

• I assume that you want to code it... For instance with python to calculate g ^ (-x) mod n you could do: import gmpy g=2 n=293829381 x=398439281 res=gmpy.invert(pow(g,x,n),n) – absinthe_minded Jan 28 '15 at 4:18
• x^(-n) = x^((-1)*n) = (x^(-1))^n $\;$ – user991 Jan 28 '15 at 8:47
• Ah, thank you very much. I thought I couldn't divide at all, since I'm not in a field. I completely forgot that $a^{-1} \text{ mod } n$ also exists when $a$ and $n$ are coprime, which, $n$ being the product of two large primes, is reasonably often the case here. – Henryk Plötz Jan 29 '15 at 1:44

There is nothing wrong with any negative exponent $\lambda$, just modular division for $(-\lambda)$, modulo $n$. That is, one would calculate modular exponentiation for positive $(-\lambda)$ first and modular inverse (division) next.
• It wouldn't be modular division for $-\lambda$, as $\lambda$ is in the exponent, no? – mikeazo Feb 2 '15 at 0:56