Cryptography: Theory and Practice:Secret Sharing Schemes | Modern Cryptography: Theory and Practice

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

Table of Contents

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

x₁	=	413	y₁	=	25439
x₂	=	432	y₂	=	14847
x₃	=	451	y₃	=	24780
x₄	=	470	y₄	=	5910
x₅	=	489	y₅	=	12734
x₆	=	508	y₁	=	12492
x₇	=	527	y₂	=	12555
x₈	=	546	y₃	=	128578
x₉	=	565	y₄	=	20806
x₁₀	=	584	y₅	=	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.

Table of Contents