0
$\begingroup$

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

Shoup, V. (2000). Practical threshold signatures. Advances in Cryptology—EUROCRYPT 2000, 207–220. Retrieved from http://link.springer.com/content/pdf/10.1007/3-540-45539-6_15.pdf

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?

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – absinthe_minded Jan 28 '15 at 4:18
  • 2
    $\begingroup$ x^(-n) = x^((-1)*n) = (x^(-1))^n $\;$ $\endgroup$ – user991 Jan 28 '15 at 8:47
  • $\begingroup$ 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. $\endgroup$ – Henryk Plötz Jan 29 '15 at 1:44
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It wouldn't be modular division for $-\lambda$, as $\lambda$ is in the exponent, no? $\endgroup$ – mikeazo Feb 2 '15 at 0:56
  • $\begingroup$ @mikeazo thanx. $\endgroup$ – Vadym Fedyukovych Feb 2 '15 at 9:57

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.