Chapter 23
Special Algorithms for Protocols

23.1 Multiple-Key Public-Key Cryptography

This is a generalization of RSA (see Section 19.3) [217,212]. The modulus, n, is the product of two primes, p and q. However, instead of choosing e and d such that ed ≡ 1 mod ((p - 1)(q - 1)), choose t keys, K_i, such that

K₁ * K₂ *...* K_t ≡ 1 mod ((p - 1)(q - 1))

Since

M^K1*K2*...*Kt = M

this is a multiple-key scheme as described in Section 3.5.

If, for example, there are five keys, a message encrypted with K₃ and K₅ can be decrypted with K₁ , K₂ , and K₄:

C = M^K3*K5 mod n

M = C^K1*K2*K4 mod n

One use for this is multisignatures. Imagine a situation where both Alice and Bob have to sign a document for it to be valid. Use three keys: K₁, K₂ , and K₃. The first two are issued one each to Alice and Bob,and the third is made public.

(1)  First Alice signs M and sends it to Bob.

M' = M^K1 mod n

(2)  Bob can recover M from M'.

M = M'^K2*K3 mod n

(3)  He can also add his signature.

M" = M^'K2 mod n

(4)  Anyone can verify the signature with K₃ , the public key.

M = M"^K3 mod n

Note that a trusted party is needed to set this system up and distribute the keys to Alice and Bob. Another scheme with the same problem is [484]. Yet a third scheme is [695,830,700], but the effort in verification is proportional to the number of signers. Newer schemes [220,1200] based on zero-knowledge identification schemes solve both shortcomings of the previous systems.

23.2 Secret-Sharing Algorithms

Back in Section 3.7 I discussed the idea behind secret-sharing schemes. The four different algorithms that follow are all particular cases of a general theoretical framework [883].

LaGrange Interpolating Polynomial Scheme

Adi Shamir uses polynomial equations in a finite field to construct a threshold scheme [1414]. Choose a prime, p, which is both larger than the number of possible shadows and larger than the largest possible secret. To share a secret, generate an arbitrary polynomial of degree m -1. For example, if you want to create a (3,n)-threshold scheme (three shadows are necessary to reconstruct M),generate a quadratic polynomial

(ax² + bx + M) mod p

where p is a random prime larger than any of the coefficients. The coefficients a and b are chosen randomly; they are kept secret and discarded after the shadows are handed out. M is the message. The prime must be made public.

The shadows are obtained by evaluating the polynomial at n different points:

k_i = F(x_i)

In other words, the first shadow could be the polynomial evaluated at x = 1, the second shadow could be the polynomial evaluated at x = 2, and so forth.

Since the quadratic polynomial has three unknown coefficients, a, b, and M, any three shadows can be used to create three equations. Two shadows cannot. One shadow cannot. Four or five shadows are redundant.

For example, let M be 11. To construct a (3, 5)-threshold scheme, where any three of five people can reconstruct M, first generate a quadratic equation (7 and 8 were chosen randomly):

F(x) = (7x² + 8x + 11) mod 13

The five shadows are:

k₁ = F(1) = 7 + 8 + 11 ≡ 0 (mod 13)

k₂ = F(2) = 28 + 16 + 11 ≡ 3 (mod 13)

k₃ = F(3) = 63 + 24 + 11 ≡ 7 (mod 13)

k₄ = F(4) = 112 + 32 + 11 ≡ 12 (mod 13)

k₅ = F(5) = 175 + 40 + 11 ≡ 5 (mod 13)

To reconstruct M from three of the shadows, for example k₂ , k₃ , and k₅ , solve the set of linear equations:

a * 2² + b * 2 + M ≡ 3 (mod 13)

a * 3² + b * 3 + M ≡ 7 (mod 13)

a * 5² + b * 5 + M ≡ 5 (mod 13)

The solution will be a =7, b =8, and M =11. So M is recovered.

This sharing scheme can be easily implemented for larger numbers. If you want to divide the message into 30 equal parts such that any six can get together and reproduce the message, give each of the 30 people the evaluation of a polynomial of degree 6.

F(x) = (ax⁶ + bx⁵ + cx⁴ + dx³ + ex² + fx + M) mod p

Six people can solve for the six unknowns (including M); five people cannot learn anything about M.

The most mind-boggling aspect of secret sharing is that if the coefficients are picked randomly, five people with infinite computing power can’t learn anything more than the length of the message (which each of them knows anyway). This is as secure as a one-time pad; an attempt at exhaustive search (that is, trying all possible sixth shadows) will reveal that any conceivable message could be the secret. This is true for all the secret-sharing schemes presented here.

Vector Scheme

George Blakley invented a scheme using points in space [182]. The message is defined as a point in m-dimensional space. Each shadow is the equation of an (m -1)-dimensional hyperplane that includes the point. The intersection of any m of the hyperplanes exactly determines the point.

For example, if three shadows are required to reconstruct the message, then it is a point in three-dimensional space. Each shadow is a different plane. With one shadow, you know the point is somewhere on the plane. With two shadows, you know the point is somewhere on the line formed where the two planes intersect. With three shadows, you can determine the point exactly: the intersection of the three planes.