How to Share a Secret

This section is an interlude in the sense that actually no protocol will be presented. However, the technique discussed is used also in many cryptographic protocols.

We say that t parties A_t, i = . . . , t, k-share a secret c, 1 < k < t, iff the following conditions (l)-(3) are satisfied.

(1) Each A_i knows some information a_i not known to the parties Aj,j ^ /.

(2) The secret c can be easily computed from any k of the a-s.

(3) The knowledge of any k — 1 of the a-s, no matter which ones they are, leaves c undetermined.

A set {a,,..., a,} satisfying (2)—(3) is referred to as a (k, t) threshold scheme for c. A possible setup for managing c will be discussed in Example 6.1.

The practical applicability of threshold schemes is obvious. For instance, c might contain instructions for some crucial action. To initiate this action, the consensus of at least k parties is needed. On the other hand, any k parties may undertake the action quite independently of whether the other parties agree or disagree.

Examples from different areas of mathematics can be given, where an object is determined by k facts from a certain collection of facts, any additional facts being superfluous. Such examples can be used for the construction of threshold schemes. Perhaps the simplest and also very easily presentable example is based on modular arithmetic and the Chinese Remainder Theorem.

Let m„ i = 1, . . . , t, be integers > 1 such that (m,, mj) = 1 whenever i # j. Let a_t, i = 1,. .., t, be integers with 0 < a_{ < m_f. (In fact, a- s could equally well be arbitrary integers.) Let M be the product of all the m/s. Denote further M_i = M/m„ and let N_t be the inverse of M_; (mod m_;), for / = 1,.. ., t. Thus, M.-N,- = 1 (mod m_;). The inverse exists and is immediately found by Euclid's algorithm because (M_i,m_i)= 1.

The congruences

x = a_t (mod m₍), i = 1,. . . , t, possess a simultaneous solution

x=t OjMjNi . i= 1

Moreover, the solution is unique in the sense that any other solution y satisfies

(y, mod M) = (x, mod M).

(Observe that this gives also a proof for the Chinese Remainder Theorem. Clearly, any two solutions must be congruent to each other (mod M). It is obvious that x is a solution because M_i is divisible by every trtj with j # i.)

Let now k be fixed, 1 < k < t. Denote by min(fc) the smallest product with k distinct factors m_t. Thus, min(fc) = m₁ . . . m_k if the m- s are in increasing order. Similarly, denote by max(k — 1) the largest product with k — 1 factors m_f. We assume that

(*) min(fc) — max(fc — 1) > 3-max(fe — 1).

(Preferably, the m,'s are chosen in such a way that this difference is large.) Let c be an integer satisfying

max(k — 1) < c < min(fc).

Define the numbers a_t by

Oj = (c, mod m₍), i = 1,.. ., t. Theorem 6.1. The set {a₁,... ,a,} is a (k, t) threshold scheme for c.

Proof. Assume first that any k of the a,'s, say a_lf... ,a_k, are known. Denote M' = m, . .. m_k, M\ = M'/mi = 1,..., k, and let N[ be the inverse of M\ (mod m_;). Defining

y=t "MN'i, i= 1

we infer by the Chinese Remainder Theorem that

y = c (mod M').

Since M' > min(/c) > c, we obtain

c = (y, mod M'),

which shows how c can be computed from the numbers a_lt... ,a_k.

Assume, secondly that only k — 1 of the a,'s, say a_l,. . ., a_k _,, are known. We define y as before, this time using only the moduli m„ . . . ,m_k__l and conclude that

y = c (mod m, ... m_k__l).

But now this leaves many possibilities for c, because of (*). Indeed, there are altogether

(**) [(min(fc) - max(fc - 1) - 1 )/m, . . .

possibilities which is a very large number if the m/s are large and close to one another.

Example 6.1. Choose k = 3, t = 5 and

m, = 97, m₂ = 98, m₃ = 99, m₄ = 101, m₅ = 103 .

Then min(fc) = 941094, max(k - 1) = 10403, and (**) ranges between 89 and 97, depending on the choice of the two m- s. The highest value 97 is obtained for the product m,m₂ = 9506, and the lowest value 89 for the product 10403. The secret c is a number satisfying

10403 < c < 941094 .

Assume that a general agency knows c and has given the parties A_t the values

a_i = 62, a₂ =4, a₃ = 50, a₄ = 50, a₅ = 38 .

The moduli m, can be assumed to be public, or else one can assume that each m, is known to the party A_t only. In the latter case the central agency who handles the secret c and gives the partial information to the parties A_{ has also taken care of that the mls satisfy the required conditions.

Assume now that A₂, A₃ and A₄ want to combine their knowledge to find out c. First they compute

M\= 9999, M'₂ = 9898, M'₃ = 9702, N\ = 33, N'₂ = 49, N'₃ = 17.

Hence,

_y = 4-9999-33 + 50-9898-49 + 50-9702-17 = 33816668 and, consequently,

c = (y, mod 98 • 99 • 101) = (y, mod 979902) = 500000 .

Similarly, if A_x, A_a and A_s want to find out c, they compute

Mi = 10403, M'₂ = 9991, M'₃ = 9797, N\ = 93, JV'₂ = 63, N'₃ = 43 ,

y = 62-10403-93 + 50-9991 -63 + 38-9797-43 = 107463646 ,

c = {y, mod 97 • 101 • 103) = 500000 .

On the other hand, A₂ and A_s only find out that

y = 4-103-59 + 38-98-41 = 176992 = 5394 = c(mod 10094),

after which A₂ and A_s know only that c is one of the numbers

5394 + /-10094, 1 < i < 92 ,

even if they know all the moduli m₍. The correct value of i is i = 49. Similarly, if A₃ and A₄ combine their knowledge, they find out that

y = 50-101 -50 + 50-99-50 = 500000 = 50 (mod 9999).

This tells them, provided they know the moduli m_f, that c is one of the numbers

50 + / • 9999, 2 < i < 94 .

Of course, they have no way of knowing that they actually hit the correct value of c when computing yl □

Date: 2015-02-16; view: 754