Attack on Verifiable Secret Sharing scheme

From: Ann Brandon (ann_brandon_spamfree_at_yahoo.com)
Date: 07/28/05


Date: Thu, 28 Jul 2005 20:54:55 +0200

Hi group,

this question is somehow related to my question from yesterday, but I
hope you can understand it without reading my former postings.

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?

In fact, an adversary knows the difference d= a_0-a'_0 = s_j -s'_j of
the secrets, but will this help in reconstruction the secrets? Is there
any other problem beside the knowledge of the difference?

Thanks for your time,
Ann