Wrong verification with Pedersen verifiable secret sharing

ru flag

According to section 4.2 of Pedersen's verifiable secret sharing, given a secret share $(s_i, t_i)$, it is possible to verify that the secret share is valid by using the commitments $E_j$, for $j=0,\ldots,k-1$, by using the formula

$E(s_i, t_i) = E_0 \cdot E_1^{x_i} \cdots E_{k-1}^{x_i^{k-1}}$, i.e. $g^{s_i}h^{t_i}=g^{a_0}h^{b_0} \cdot (g^{a_1}h^{b_1})^{x_i} \cdots (g^{a_{k-1}}h^{b_{k-1}})^{x_i^{k-1}}$.

The following Go method performs the verification step according to Pedersen VSS:

type SecretPart struct {
    s *big.Int
    t *big.Int

type Pedersen struct {
    threshold int
    p         *big.Int
    g         *big.Int
    h         *big.Int

func (p Pedersen) verify(abscissa *big.Int,
    part SecretPart,
    commitments []*big.Int,
) error {
    pMinus := new(big.Int).Sub(p.p, big.NewInt(1))
    // rhs = E_0 * E_1^x * ... * E_j^{x^j}
    rhs := new(big.Int).Set(commitments[0])
    xPow := big.NewInt(1)
    for j := 1; j < p.threshold; j++ {
        xPow.Mul(xPow, abscissa).Mod(xPow, pMinus)
        term := new(big.Int).Exp(commitments[j], xPow, p.p)
        rhs.Mul(rhs, term).Mod(rhs, p.p)

    // lhs = g^s * h^t
    term1 := new(big.Int).Exp(p.g, part.s, p.p)
    term2 := new(big.Int).Exp(p.h, part.t, p.p)

    lhs := new(big.Int).Mul(term1, term2)
    lhs.Mod(lhs, p.p)

    if lhs.Cmp(rhs) != 0 {
        return fmt.Errorf("wrong secret part: lhs=%s != rhs=%s", lhs, rhs)

    return nil

Despite the procedure is straightforward, the verification step always fails having the left-hand side term different from the right-hand side one.

Here is a Go Playground with a running show case.

sb flag

Your $g$ and $h$ are not generators of the subgroup of order $q = (p-1)/2$ (in your implementation, you have $p=83$, $q=41$, $g=2$, and $h=8$). The order of $g$ and $h$ is $p-1 = 82$ rather than $q=41$.

For Pedersen commitments, you want to work in the group of order $q$, which requires using $g=3$ and $h=7$ and setting your "pMinus1" variable to be $q=41$ (when using your toy parameter $p=83$).

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


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.