|
![](/images/dotclear.gif) |
[an error occurred while processing this directive]
Exercises
- 11.1 Write a computer program to compute the key for a Shamir (t, w)-threshold scheme implemented in
. That is, given t public x-coordinates, x1, x2, . . . , xt, and t y-coordinates y1, . . . , yt, compute the resulting key. Use the Lagrange interpolation method, as it is easier to program.
- (a) Test your program if p = 31847, t = 5 and w = 10, with the following
shares:
x1
| =
| 413
| y1
| =
| 25439
|
x2
| =
| 432
| y2
| =
| 14847
|
x3
| =
| 451
| y3
| =
| 24780
|
x4
| =
| 470
| y4
| =
| 5910
|
x5
| =
| 489
| y5
| =
| 12734
|
x6
| =
| 508
| y1
| =
| 12492
|
x7
| =
| 527
| y2
| =
| 12555
|
x8
| =
| 546
| y3
| =
| 128578
|
x9
| =
| 565
| y4
| =
| 20806
|
x10
| =
| 584
| y5
| =
| 21462
|
Verify that the same key is computed by using several different subsets of five shares.
- (b) Having determined the key, compute the share that would be given to a participant with x-coordinate 10000. (Note that this can be done without computing the whole secret polynomial a(x).)
- 11.2 A dishonest dealer might distribute bad shares for a Shamir threshold scheme, i.e., shares for which different t-subsets determine different keys. Given all w shares, we could test the consistency of the shares by computing the key for every one of the
t-subsets of participants, and verifying that the same key is computed in each case. Can you describe a more efficient method of testing the consistency of the shares?- 11.3 For access structures having the following bases, use the monotone circuit construction to construct a secret sharing scheme with information rate ρ = 1/3.
- (a) Γ0 = {{P1, P2}, {P2, P3}, {P2, P4}, {P3, P4}}.
- (b) Γ0 = {{P1, P3, P4}, {P1, P2}, {P2, P3},{P2, P4}}.
- (c) Γ0 = {{P1, P2}, {P1, P3}, {P2, P3, P4}, {P2, P4, P5}, {P3, P4, P5}}.
- 11.4 Use the vector space construction to obtain ideal schemes for access structures having the following bases:
- (a) Γ0 = {{P1, P2, P3}, {P1, P2, P4}, {P3, P4}}.
- (b) Γ0 = {{P1, P2, P3}, {P1, P2, P4},{P1, P3, P4}}.
- (c) Γ0 = {{P1, P2}, {P1, P3}, {P2, P3}, {P1, P4, P5}, {P2, P4, P5}}.
- 11.5 Use the decomposition construction to obtain schemes with specified information rates for access structures having the following bases:
- (a) Γ0 = {{P1, P3, P4}, {P1, P2}, {P2, P3}}, ρ = 3/5.
- (b) Γ0 = {{P1, P3, P4}, {P1, P2}, {P2, P3},{P2, P4}}, ρ = 4/7.
|