Wrong verification with Pedersen verifiable secret sharing

Morpheus

6/7/24, 5:26 PM

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.

1 + 0

secret-sharing

Score:2

Crypto

Sacha Servan-Schreiber

6/7/24, 5:59 PM

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

+ 0

Elon Musk

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

EN: Wrong verification with Pedersen verifiable 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.