2
$\begingroup$

I'm playing around with implementing Shamir's secret sharing scheme in Kotlin.

Here is implementation so far:

fun main(args: Array<String>) {

val a = 10.0.toBigDecimal()
val b = 10.0.toBigDecimal()
val c = 7.0.toBigDecimal() // secret
val field = 20.0.toBigDecimal()
 fun polynomial() : (BigDecimal) -> BigDecimal =
    { x : BigDecimal -> ((a * x.pow(2))+(b*x)+c).remainder(field)}

fun generateShares(one :BigDecimal, two : BigDecimal, three :BigDecimal): List<Pair<BigDecimal,BigDecimal>> {
    var shareSet = arrayOf(one,two,three)
    return shareSet.map { x ->  Pair(x, polynomial().invoke(x)) }
}

val shares = generateShares(1.0.toBigDecimal(), 2.0.toBigDecimal(), 3.0.toBigDecimal())

fun langraged(cord0 : Pair<BigDecimal,BigDecimal>,cord1 : Pair<BigDecimal,BigDecimal>,cord2 : Pair<BigDecimal,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, field -> // This lambda is what I am asking about
        val resser = cord0.second * L0(x) + cord1.second * L1(x)  + cord2.second * L2(x)
        if (resser < 0.0.toBigDecimal()){
            (resser % field) + field}
        else {
            resser % field
        }
    }
}

val constructedPolynomial = langraged(shares[0], shares[1], shares[2])

val reConstructedSecret = constructedPolynomial(0.0.toBigDecimal(), field)


println("and we reconstruct f(0) as: " + reConstructedSecret)

}

So the gist of my question here is about the usage of my field size, that I use for modulo.

With this implementation, if I choose a field that is larger than my secret then I will only be able to reconstruct the part of the secret that is remainder after dividing by the field size.

In other words, In order to reconstruct my polynomial, when using a field I have to return

result % field 

So for example, if my field is 50, and my secret 51, then my reconstructed secret is 1.

So, in order to use Shamir's scheme with a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

$\endgroup$
3
  • 1
    $\begingroup$ Quick intro to poncho's answer: no, the field size needs not be larger than the secret. A common alternative is to split the secret into smaller fragments (e.g. bytes, 4-bit nibbles, or bits) that can be represented as field elements, each individually split into shares. That way a small field will do, as long as it's suitable for a segment of the shared secret. $\endgroup$
    – fgrieu
    Mar 20 at 7:00
  • $\begingroup$ In this model, would a single share then consist of coordinates from several polynomials? $\endgroup$ Mar 20 at 12:37
  • 1
    $\begingroup$ Yes. In this model, each segment of the secret is encoded as one coefficient in each share. A share is the concatenation of the coefficients of that share, e.g. in the same order as the segments of the secret. $\endgroup$
    – fgrieu
    Mar 20 at 14:20
4
$\begingroup$

So the gist of my question here is about the usage of my field size, that I use for modulo.

Well, the first thing to notice is the definition of a 'field' (which is a term from mathematics); I don't feel like getting into a discussion of what a field is (look it up in Wikipedia if you're interested), however addition and multiplication modulo a composite (such as 50) is not a field, and Shamir Secret Sharing won't work there.

If you replace 50 with 53 (which is prime), then it would work.

In practice, we often use a extension field $GF(2^k)$ for $k$ perhaps 8 or 16 or 32; that makes things nicely line up in bytes, however the operations are not modulo the field size (the 'addition' operation is actually exclusive-or, and the multiplication operation is significantly different than what you're used to). Of course, it's up to you if you want to look into that; you might want to learn the basics with a prime field (which is what you're using) first.

In any case, to address your question:

So, in order to use Shamir's scheme with a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

Well, a single iteration of Shamir's secret sharing will always return a field element (that can be interpreted as a value between 0 and the field size minus one); hence if you need to share a secret that may be larger than the field size, we generally divide the secret into a number of smaller secrets, and share each subsecret independently.

For example, if you have a 16 byte secret, we may divide that into the 16 values of one byte each; for each byte value, we may generate a secret polynomial modulo 257 (a prime), and distribute shares for that. When it comes time to reconstruct, we construct each of the byte values independently, and then concatenate them to form the original 16 byte secret.

Just a word of warning: you must generate an independent secret polynomial for each byte - reusing the same polynomial (except for the constant term) breaks the system. On the other hand, you can use the same $x$ coordinate for each of the subsecrets when you give a share to someone.

Now, with $p=257$, each share will be somewhat larger than the original secret (because each secret share is a value between 0 and 256; that doesn't quite fit into a byte). That's why using $GF(256)$ is popular; each secret share is a value between 0 and 255, and so everything fits nicely...

$\endgroup$
1
  • $\begingroup$ thanks a lot! thats was a really extensive answer $\endgroup$ Mar 20 at 11:54

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.