| Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
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.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC