0
$\begingroup$

im doing a small programming project, where I have to implement shamirs secret sharing scheme.

I want to share the secret S = 21426848149916227113669602 I want a k of three, meanng that three shares can recontruct my secret, so I need a second degree polynomium. First I create my function of the form:

f(x) = ax^2 + bx + c

and pick random values 8 and 10 for a and b. I then plot my secret in for c, which is where f(0)

 f(x) = 8x^2 + 10x + 21426848149916227113669602

I then create three shares by generating 3 integers between 1-5, as an example. this can results in the following shares as points

(3.0, 21426848149916227113669704.000)
(4.0, 21426848149916227113669770.000)
(2.0, 21426848149916227113669654.000)

And now using these three points, I can reconstruct my function, and call f(0). If ayone would like to see, this is how I have implemented it in kotlin:

fun langraged(cord0 : Pair<BigDecimal,BigDecimal>,cord1 : Pair<BigDecimal,BigDecimal>,cord2 : Pair<BigDecimal,BigDecimal>) : (BigDecimal) -> BigDecimal{
    val L0: (BigDecimal) -> BigDecimal = { x -> ((x - cord1.first)*(x - cord2.first)) / ((cord0.first - cord1.first)*(cord0.first - cord2.first))}
    val L1: (BigDecimal) -> BigDecimal = { x -> ((x - cord0.first)*(x - cord2.first)) / ((cord1.first - cord0.first)*(cord1.first - cord2.first))}
    val L2: (BigDecimal) -> BigDecimal = { x -> ((x - cord0.first)*(x - cord1.first)) / ((cord2.first - cord0.first)*(cord2.first - cord1.first))}

    return { x -> cord0.second * L0(x) + cord1.second * L1(x)  + cord2.second * L2(x) }
}

But here's is the thing, if I choose some other values for a and b, it fails once in a while in reconstructing f(0), with output values that are just slightly off. THe same starts happening when I generate my shares in a higher interval than 1-5.

Am I missing some important points in how I am picking these parameters to the secret sharing scheme?

Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ This is an artifact of using floats. A computer can not represent a real number with arbitrary precision, so rounding errors will happen. You could use some sort of rational library, but to be secure, shamir's secret sharing needs to be done over a finite field $\endgroup$
    – Aman Grewal
    Commented Mar 16, 2021 at 18:48
  • $\begingroup$ cool, thanks a lot. Do you think my problem is more likely to be an issue of the numbers reprentation (im currently using Bigdecimal type, which should be fairly precise) or the fact that I should use a field (which I am quite unsure what actually means, all the articles about it just says that you need to make a polynomial over a field, but does not mention what that actually means) $\endgroup$
    – crypto_confuse
    Commented Mar 17, 2021 at 15:54
  • $\begingroup$ I'm not familiar with kotlin or its libraries. You'd need a rational library that stores numbers as (numerator, denominator) for this to always work. Or you can try to find a library for finite field math. (Alternatively, you can make either of these yourself if you can't find them. They're not hard if you don't care about speed.) You might have more luck learning about finite fields by searching for modular arithmetic. $\endgroup$
    – Aman Grewal
    Commented Mar 17, 2021 at 20:33
  • $\begingroup$ Hmm, I really dont think the problem is the numbers representation $\endgroup$
    – crypto_confuse
    Commented Mar 17, 2021 at 22:09
  • $\begingroup$ Also, it should work without using field arithemtic. I know that it will not be as safe, but i am just trying to get it to work, which it currently doesnt. It would be nice if someone actually looked at these numbers to see if they can spot the problem $\endgroup$
    – crypto_confuse
    Commented Mar 17, 2021 at 22:11

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.