Understanding Feldman's VSS with a simple example

Question

I'm trying to understand Feldman's VSS Scheme. The basic idea of that scheme is that one uses Shamir secret sharing to share a secret and commitments of the coefficients of the polynomial to allow the other party to verify that the share they received is valid. I implemented it in code following the wikipedia page, but my verification function doesn't work. Here is a simple example of the failure:

We will work in the field $\mathbb{Z}_{11}$ with generator $g=3$. Let $f(x)=5+3x+8x^2$ be our Shamir polynomial. Thus $f(1)=5$. So let $s_1=5$ be the share that party $p_1$ gets.

The dealer also must commit to the coefficients. So the commitments are $3^5=1, 3^3=5, 3^8=5$. (These are computed as $g^c$ for each coefficient $c$ of the polynomial).

For verification that $s_1$ is correct, we compute $g^{s_1}=3^5=1$ and compare this to $1*5*5=3$ (the exponents are all $1$ since $i=1$, otherwise this step is done as $k^{i^j}$ where $k$ is the commitment, $j$ is the index of the commitment). Since $1\neq3$, the verification fails. But why? It should pass assuming I have done things correctly.

Update
So working the math a little in more detail:
$g^{s_1}=1$ and $g^5 g^{3^{1^1}} g^{8^{1^2}}= g^{5+3^{1^1}+8^{1^2}}= g^{5+3\cdot 1^1 + 8\cdot 1^2} = g^{16} = g^6 = 3$ and $1\neq 3$.

Note that the exponent is $f(1)$. Wikipedia offers a small hint:

(Typically, one takes a subgroup of $\mathbb{Z}_q^*$, where $q$ is a prime such that $q$ divides $p-1$.

Is my problem that I am not working in such a subgroup? If so, why does it not work in general for $\mathbb{Z}_p$ (Wikipedia only says that typically one works in this subgroup)? Is there a standard way to set up such a subgroup?

Answer 1

It has to do with which modulus you use. You did all your arithmetic modulo 11. However, when using Feldman's VSS, you gotta use two different moduli (using each one in the appropriate spot). In your example, you shouldn't do all arithmetic modulo 11. Instead, you should be doing some arithmetic modulo 11, and some arithmetic modulo 5 (the order of $g$ in this case). If you do that, everything will work out.

In general, you need to pick primes $p,q$ such that $q | p-1$. Then, some arithmetic is done modulo $p$, and some arithmetic is done modulo $q$. In particular:

• The polynomial $f(x)$ is treated modulo $q$, so when you compute the shares, you need do arithmetic modulo $q$.

• The commitments and all computations with the commitments are treated modulo $p$, so when you verify that you got the correct share, you work modulo $p$.

The reason we do it this way is that when doing a computation like $3^{15}$ (modulo $11$), we can reduce the base modulo 11, but we have to reduce the exponent modulo 10. Roughly speaking, commitments are in the base, whereas the value of the polynomial (the shares; the coefficient of the polynomial) are in the exponent -- so you gotta use different moduli for these two different kinds of values.

We can modify your example to take this into account. We could take $p=11$, $q=5$, and generator $g=3$ of the subgroup of order $q$ of $(\mathbb{Z}/p\mathbb{Z})^*$. However, you can no longer have the polynomial $f(x)=5+3x+8x^2$: the polynomial is interpreted modulo $q$, so all coefficients have to be in the range $0..4$. This means we'll need to change things a little bit.

So, here's a corrected example. You could use the polynomial $f(x)=0+3x+3x^2$. Since $f(1)=1$, you'll get the share $s_1=1$. The commitments are $3^0=1$, $3^3=5$, and $3^3=5$.

For verification of the correctness of the share, we first compute $3^{s_1}=3^1=3$. Next, we compute the check value $1 \times 5^1 \times 5^{1^2} = 3$. You can see that $3^{s_1}$ is equal to the check value, so everything verifies, and the share is correct.