2
$\begingroup$

What is the implication of not using the Lagrange multipliers in Shamir's secret sharing?

I mean each update will be $Poly(x_i) \bmod p$ where $p$ is a prime number instead of the original one that is $(Poly(x_i)* LPC_i) \bmod p$. Assuming that the verifier has access to all secrets $x_i$s, it can re-do all the updates and check if the result is equal to the secret or not.

Is that less secure?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ But then, how are you interpolating your polynomial $Poly$, being given the points $(x_i, Poly(x_i))$? If the question is "can I use other interpolation methods", then yes, you can. iirc, the Lagrange way is generally easier when you know in advance how many terms you need to have enough accuracy, which is the case in Shamir's secret sharing. $\endgroup$
    – Lery
    Commented Jun 23, 2017 at 22:20

1 Answer 1

Reset to default
2
$\begingroup$

I will answer you by an example, assuming Shamir sharing algorithm with $d=2$ (minimum shares). So, by definition we need a $d-1$ degree polynomial as:

$Poly(x)$ = $ A_1 \cdot X^1 + S$ = $10x +20 $ where $S=20$ is the secret. The dealer will calculate the shares as (two shares for simplicity, where 2 is needed to reconstruct the polynomial):

$(1) [x_1, Poly(x_1) ]$ = $[ 5, Poly(5)]$ =$[5,70]$ , and

$(2) [x_2, Poly(x_2) ]$ = $[ 10, Poly(10)]$ =$[10,120]$.

Now, without using Lagrange interpolation: the verifier needs to reconstruct the polynomial equation (i.e., line equation) to find $S$ as:

$(1) Poly(5)=A_1 \cdot 5 +S =70$ and

$(2) Poly(10)= A_1 \cdot 10 + S =120$

So, you will need to solve the two equations. This is a simple one because it has only two equations. However, for larger $d$ minimum shares it will be intricate process to solve lets say 10 equations.

Second, by using Lagrange interpolation it will be much easier because we are only interested by $Poly(0) \equiv S $.

In conclusion, both have the same security but Lagrange interpolation is much faster way.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer. I assume the verifier has a fair amount of computation power. Even if it is 10 equations, it will be 10 equations 10 variables, which is very easy to solve (matrix inversion). right? $\endgroup$
    – Masood_mj
    Commented Jun 24, 2017 at 2:05
  • $\begingroup$ Also I'm looking in a different setting where we want to make sure all parties saw a document. Each party should add the output of polynomial to X (as a cumulative signature). In case we use Lagrange multipliers, the final value will be equal to S and the verifier can verify that all parties have seen the doc. If we don't use the multipliers, the verifier (that knows polynomial, x1 and x2), performs the computation again and makes sure it is equal to X. $\endgroup$
    – Masood_mj
    Commented Jun 24, 2017 at 2:15
  • 1
    $\begingroup$ Regarding computation it is ok if the user have good computation power, as i said lagrange provides faster way. However, regarding the other need that you want users to prove they have seen a document, I dont think secret sharing is the right primitive. Maybe, you can look for Pedersen commitments which provide homomorphic properties that can work for you scenario. Lastely, if my response answered your question you can check it. $\endgroup$
    – NuminousName
    Commented Jun 24, 2017 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.