Re: Attack on Verifiable Secret Sharing scheme

From: Aldar C-F. Chan (aldar_at_comm.utoronto.ca)
Date: 07/28/05 

Date: Thu, 28 Jul 2005 19:48:32 GMT

"David Wagner" <daw@taverner.cs.berkeley.edu> wrote in message
news:dcbars$jng$1@agate.berkeley.edu...
> Ann Brandon wrote:
>>Let us consider n parties P_1, ... , P_n and a polynomial:
>>f(x) = a_0 + a_1*x + ... + a_t*x^t mod p shared by a dealer D.
>>First the values COMMIT_i = g^{a_i}, 0<=i<=t are sent to each party.
>>Then each party gets its share: s_j = f(j), 1 <=j<=n and can verify the
>>correctness of its shares.
>>
>>Later then the dealer wants to share another secret a'_0. D first
>>generates the commitment COMMIT'_0 = g^{a'_0} and sent it to every party
>>P_j. Then D creates shares:
>>s'_j =f'(j), where f'(x) = a'_0 + a_1*x + ... + a_t*x^t mod p and send
>>the share s'_j to party P_j.
>>As you see, the polynomial f and f' only differ in the constant
>>coefficient.
>>
>>Each party now holds s_j and s'_j and the commitments. Is it now
>>possible for an adversary who controls up to t partys and hence knows in
>>all 2t shares (for each polynomial t shares, but the polynomial f and f'
>>only differ in the constant coefficient) to reconstruct the secrets a_0
>>and/or a'_0?
>
> Yes, I think it is. There are t+2 unknowns (a'_0,a_0,a_1,..,a_t) and 2t
> knowns (s_j, s'_j for each corrupt party j), and the system of equations
> is linear, so the answer is that an attacker can presumably learn all
> the secrets in this setting.
>
I am sorry but there are actually only t+1 independent linear equations.
Since the two equations of each user can reduce to the original one and
the other being (s_j - s_j ) being some value.