Why modular arithmetic in secret sharing?

Question

I learned about how secret sharing works in my math class today. From what I understand about the way I was taught it's possible to implement it, I can choose a secret number $N$ and generate a polynomial $P(x)$ such that $P(0)=N$.

To generate the polynomial, I would simply consider how many people I want to have to come to discover the secret, $n+1$. So I would create $n$ random numbers, and, along with the secret value at 0, this would form the values for $P(x)$ for $x \in \{0, \dots, n\}$. Those $n+1$ numbers would determine a polynomial of degree $n$, and using that polynomial, I could generate as many more numbers as I wanted to distribute to people, but still require $n+1$ people to come together to discover the secret.

Sorry for the long explanation, but I also hope that if my reasoning above isn't sound, I can get help. The actual part I'm confused about (my question): why, in my class, did the professor present everything $\mod p$? Everything I find online also has secret sharing implemented modulo some prime. How does that help the algorithm?

Thanks!

Answer 1

I don't know many things about cryptography, but I suspect that the reason is probably because on a finite field, every calculation become easier in the sense that numbers will not become larger than $p$.

To calculate $P(0)$, one may calculate the Vandermonde matrix and solve the equation involving that. If $\mathbb{Q}$ was used instead of a finite field, the calculation can be done, but the numbers created during calculation would be very big. (If $n = 100$ and an $x$ is $42$, the matrix must contain numbers similar (in size) to $42^{100} \simeq 2.11 \times 10^{162}$)

On the other hand, if an 256-bit length prime number $p$ and $\mathbb{F}_p$ is used, the largest number created during calculation will not become higher than $2^{256} \simeq 1.16 \times 10^{77}$.

Answer 2

Suppose you have $d$ secret shares. I'd like to prove that you know literally nothing about the secret. (But you will know everything about the secret once you get one more share.)

If I'm working mod a prime, this is easy: there are exactly $p$ polynomials that pass through the $d$ points you know. Each one of these corresponds to a different value of the secret. So if I chose my polynomial at random, the secret is equally likely to be any of the $p$ possibilities.

If I'm not working mod a prime, this is harder to prove. Now I have to be careful: what did I mean by choosing my polynomial "at random," given that there are infinitely many possibilities? In fact, it turns out that no matter how I choose my polynomial with real coefficients, knowing even 1 share of the secret gives me at least a tiny bit of information about the secret. So that's no good.

• Posted by my GSI, not me.