Why do we need to mod in Shamir's Secret Sharing algorithm

Migwel

4/12/23, 4:54 PM

I'm looking into Shamir's Secret Sharing algorithm and it's clear to me how it works but I don't understand the exact reason why we need to find a prime number and do modulo arithmetic using that prime.

On Wikipedia, it says that if you don't use modulo arithmetic, an attacker could get some information on the value without having enough shares.

In Joy of Cryptography, it seems to justify the need of modulo arithmetic by saying that the polynomial coefficients need to be uniformly distributed in Z which is not feasible so instead we use Z_p where a uniform distribution is achievable.

On other websites (and here), I saw some people saying that the modulo was simply needed so that values would not get too big.

In short, I couldn't find one definitive reason why the modular arithmetic is truly needed. Of course, it could be a combination of all the reasons mentioned above but it is strange to me to see all these sources giving a different justification without mentioning the other reasons. So could you help me figure out why this is really needed?

123

0 + 0

secret-sharing

kelalaka

4/12/23, 5:21 PM

Another [Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme](https://crypto.stackexchange.com/q/5502/18298)

Migwel

4/12/23, 5:35 PM

Yes, both these answers help, thanks a lot! I guess searching for the `mod` keyword was wrong and I should have looked for finite field instead. Thanks a lot!

Score:0

Crypto

Wilson

4/12/23, 5:07 PM

Both of the explanations you stated are actually two sides of the same coin.

How would you sample a uniformly random element from $\mathbb{Z}$? This is an infinite set. Even if you could, it is unclear how many bytes of memory would you need to represent this random "integer?"

Thus, we need to sample coefficients from a finite set of elements (which can be represented in fixed number of bytes). However, not all finite sets will allow you to interpolate polynomials over. Thus, we need to choose a finite set that works with a known polynomial interpolation algorithm. Lagrange interpolation happens to work over finite fields (e.g. polynomials with coefficients in a finite field). The most canonical example of a finite field is the integers mod a prime number. This is the most conceptually easy representation so many texts will use this example.

0 + 0

Daniel

4/13/23, 5:37 AM

It's worth noticing that interpolation does work over arbitrary finite rings (not only finite fields) as long as they have evaluation points $\alpha_0,\ldots,\alpha_n$ such that every non-zero difference is invertible. https://crypto.stackexchange.com/questions/48928/shamir-secret-sharing-p-not-prime/96507#96507

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Why do we need to mod in Shamir's Secret Sharing algorithm

TH: ทำไมเราต้องดัดแปลงอัลกอริธึมการแบ่งปันความลับของ Shamir

RO: De ce trebuie să modificăm algoritmul Shamir's Secret Sharing

RU: Как преобразовать 33-байтовое представление в 32-байтовое представление?

VI: Tại sao chúng ta cần mod trong thuật toán Shamir's Secret Sharing

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.