1

What I would like to do is an exponentiation with a public constant $(c=9)$ to the power of a secret number $(s=4)$ without revealing it and everything with modular arithmetic.

$$c^s= 5 \pmod{11} \tag 1$$

To do it, I splitted the secret number $s$ with a secret polynomial $(y(x) = 3x^2 + 2x + s)$ using Shamir's secret sharing and get three points from it.

$$(x_i,y_i) = [(1, 9), (2, 9), (3, 4)] \pmod{11}$$

Now, I want to perform the same as in $(1)$ but with the $y_i$ part of the points

$$ y'_i = c^{y_i}$$ $$(x_i,y'_i) = [(1, 5), (2, 1), (3, 4)] \pmod{11}$$

To obtain the same result as in $(1)$ secretly, it is necessary to interpolate all points $(x_i, y_i)$ using Lagrange $(L=\sum_{i=1}^n\;y_i\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i})$ where $x=0$ but, since I'm not going to use $y_i$ instead I'm going to use $y'_i$, it is necessary to change the function raising $c$ to the power of $L$:

$$c^L=\prod_{i=1}^n\;c^\left(y_i\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i}\right)$$ $$c^L=\prod_{i=1}^n (c^{y_i})^\left(\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i}\right)$$ $$c^L=\prod_{i=1}^ny'{_i}^\left(\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i}\right) \tag 2$$

With all of that said, what is the step-by-step process of calculating the above equation $(2)$ using modular arithmetic with the points $(x_i,y'_i)$?

I tried to solve what is in the exponent with $\pmod{11-1}$ but when I did the inverse of $(x_j-x_i)$ it just didn’t work, the multiplication is fine, but the division is simply giving an incorrect number or it is not possible.

Jolo
  • 13
  • Could you provide more context? You have three points on this polynomial. OK. Then what? What is the problem you're solving? Where do the $S$ and $c^S$ come from? Any text references?? – Henno Brandsma Sep 19 '18 at 21:42
  • @HennoBrandsma I changed the post a little bit and I hope it is more understandable. The problem that I want to solve is to decrypt a cypher text with ElGamal using multiples keys with Shamir secret sharing, because one part of the decryption process in ElGamal is to raise C1 to the power of the secret key, I need to perform that with Shamir. – Jolo Sep 20 '18 at 09:24
  • The part in which I am stuck is in the calculation of the exponent $\left(\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i}\right)$, the division in the exponent gives me an incorrect number or it is not possible to find it when I work with an $\pmod{11-1}$ – Jolo Sep 20 '18 at 09:27

1 Answers1

1

Modulo $11$ we have that $$1^{-1} =1, 2^{-1}=6, 3^{-1}=4, 4^{-1} =3, 5^{-1}=9, 6^{-1} = 2, 7^{-1} = 8, 8^{-1} = 7, 9^{-1} = 5, 10^{-1} = 10$$

In every expression like $\frac{a}{b}$ write it as $a\cdot b^{-1}$ and reduce modulo $11$ again.

So your product terms of quotients become a lot multiplications modulo $11$.

Henno Brandsma
  • 242,131