Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210   Pub Date: 03/17/95

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, x₁, x₂, . . . , x_t, and t y-coordinates y₁, . . . , y_t, 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)  Γ₀ = {{P₁, P₂}, {P₂, P₃}, {P₂, P₄}, {P₃, P₄}}.

(b)  Γ₀ = {{P₁, P₃, P₄}, {P₁, P₂}, {P₂, P₃},{P₂, P₄}}.

(c)  Γ₀ = {{P₁, P₂}, {P₁, P₃}, {P₂, P₃, P₄}, {P₂, P₄, P₅}, {P₃, P₄, P₅}}.

11.4  Use the vector space construction to obtain ideal schemes for access structures having the following bases:

(a)  Γ₀ = {{P₁, P₂, P₃}, {P₁, P₂, P₄}, {P₃, P₄}}.

(b)  Γ₀ = {{P₁, P₂, P₃}, {P₁, P₂, P₄},{P₁, P₃, P₄}}.

(c)  Γ₀ = {{P₁, P₂}, {P₁, P₃}, {P₂, P₃}, {P₁, P₄, P₅}, {P₂, P₄, P₅}}.

11.5  Use the decomposition construction to obtain schemes with specified information rates for access structures having the following bases:

(a)  Γ₀ = {{P₁, P₃, P₄}, {P₁, P₂}, {P₂, P₃}}, ρ = 3/5.

(b)  Γ₀ = {{P₁, P₃, P₄}, {P₁, P₂}, {P₂, P₃},{P₂, P₄}}, ρ = 4/7.