Feldman Verifiable secret sharing verify

user109261

5/23/24, 12:56 PM

I recently started to learn about Shamir secret sharing and Feldman's VSS Scheme. I know the concepts But I can't figure out how it works. mostly because many of modulates are with "p" and some of them are with "q". I can't find a good sample that helps me understand it better.

here's the example I am working with:

assume that I want to work with $q = 59$ and my prime for Shamir secret sharing, and $secret = 22$. I have a 2 of 3 threshold SSS. and my polynomial is : $f(x) = 25x+22$. also assume that the index of participant is 12.

$f(12) = 25*12+22 = 322 = 27 \pmod{59}$

until now, this was just Shamir secret sharing. now I need to add versifications. I use $p = 709$ and we know that : $q | p - 1$. and $g = 37$ is a generator of q

now commitments:

$c_0 = g^{secret} = 37^{22} = 106 \pmod{709}$

$c_1 = g^{a_1} = 37^{25} = 670 \pmod{709}$

now, participant 1 wants to verify his share:

left side : $g^{f(12)} = 37 ^ {27} = 493 \pmod{709}$

right side : $c_0*c_1^x = 106 * 670^{12} = 196 \pmod{709}$

why are they not equal? am I doing modulates wrong?

_{I added reference to Wikipedia page of Feldman VSS scheme. should I add anymore explain about Shamir and Feldman scheme to clearify?}

0 + 5

finite-field

secret-sharing

Daniel S

5/23/24, 1:49 PM

The problem is that 37 is not of order $q$ in the multiplicative group mod 709. You can check that $37^{59}\equiv 522\pmod{709}$. Try using $g=20$ instead.

kodlu

5/23/24, 2:54 PM

while @DanielS has given a nice hint, can you *please* clearly define what the Feldman verification is, so this question is useful to others?

user109261

5/24/24, 8:16 AM

thanks for your reply @DanielS. how can I find that generator? generator of q modulus p when p and q are both primes and q | p - 1?

Daniel S

5/24/24, 11:19 AM

You pick a number and raise it to the power $(p-1)/q$ modulo $p$. If the answer is not 1 then the answer will work as a generator of a subgroup of order $q$. In this case we might pick 5 and then $5^{(p-1)/q}\equiv 20\pmod{709}$.

user109261

5/24/24, 11:37 AM

thank you. that was very helpful. @DanielS

Elon Musk

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

EN: Feldman Verifiable secret sharing verify

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.