# Should the field size in Shamir secret sharing scheme be larger than secret?

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, shares, shares)

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?

• 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.
– fgrieu
Mar 20, 2021 at 7:00
• In this model, would a single share then consist of coordinates from several polynomials? Mar 20, 2021 at 12:37
• 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.
– fgrieu
Mar 20, 2021 at 14:20

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.

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...