Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 4 down vote accepted
+50

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.

share|improve this answer
    
Awesome, that helped a lot. Is there a proper way to generate secure values for $p,q$? Basically we would one $p-1$ to have a large prime factor I'm assuming. But we'd also need to know that factor. Or even better, is there a semi-standard $p,q$ that will work? – mikeazo Mar 11 '13 at 16:42
1  
All you need is that $p,q$ are both prime and that the discrete logarithm in the size-$q$ subgroup of $(\mathbb{Z}/p\mathbb{Z})^*$ is hard. This is the same as the requirement for, e.g., ElGamal or DSA. So, use any standard algorithm for generating such $p,q$, or any such $p,q$. Or, randomly pick a random 160-bit value $q$, test if it is prime, pick a random 1888-bit value $k$, and test if $p=kq+1$ is prime; repeat until both $p,q$ are prime (there are ways to optimize this so it runs faster, but this will work). – D.W. Mar 11 '13 at 20:59
1  
@mikeazo, that's correct. With those parameters, the Legendre symbol doesn't leak anything about $s$: the Legendre symbol $(g^s|p)$ will always be $1$, regardless of $s$, so no leakage. Actually, with those parameters, I don't see any way that $g^s$ leaks anything about $s$, so I don't know what the Wikipedia comment is referring to. (Maybe it's what happens if you don't choose $p,q$ that way? Maybe it's the fact that you can verify a guess at $s$ using $g^s$? Or something else entirely? The statement is unsourced, so I can't tell.) – D.W. May 16 '13 at 18:15
1  
@hanugm, That works in this case. – mikeazo Jun 9 at 13:26
2  
@hanugm, it isn't my answer. It is the answer I accepted. But I fail to see your point. $g=3$ is a generator of a subgroup of order $5$. The answer does not claim that it is a generator of order $11$. – mikeazo Jun 9 at 14:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.