From: peter.allan@aeat.co.uk (Peter M Allan)
Date: Sat, 10 Aug 1996 04:23:16 +0800
To: cypherpunks@toad.com
Subject: secret sharing protocol - new or reinvented ?
Message-ID: <9608091638.AA17409@clare.risley.aeat.co.uk>
MIME-Version: 1.0
Content-Type: text/plain




Schneier in That Book 2nd Ed p73
refers to "secret sharing with disenrollment",
but without giving details of such a scheme.

He gives a reference [1004] I think, by K Martin,
which has about 10 pages on the subject.
But I have not got it.

I planned a "secret sharing with disenrollment"
scheme last night.  Here is a brief description
and if somebody with the book tells me it's new
 (unlikely I think)
I'll write it up in more formally.  It has a 
resemblance to S/Key, but in the other direction
and using a keyed hash function.

If you see snags with this, I'd like to know.


Peter Allan  peter.allan@aeat.co.uk






Trent chooses his shareholders, a block cypher (or keyed hash),
a threshold, and a number of steps.  The threshold should be more
than half the number of shareholders.

(Say 15 shareholders for a 10 out of 15 scheme,
using DES, over 20 steps.)

Trent generates 15 64-bit DES keys (not caring about parity),
and gives them securely one to each shareholder.  He introduces all
shareholders to each other so they can recognise each other later.
He also tells them the number of steps (here 20).

Trent (in possession of all shares) calculates the secret, which
is a 64-bit number.  Obviously this could just be a key for a
secret not yet created at share distribution time.

Secret calculation is performed by executing the required number
of steps, and the result of the last step is the secret. 

Disenrollment (conducted by shareholders, presumably under
orders from Trent) is the performance of one step, omitting
those to be disenrolled.  (The number of possible disenrollments
is limited by the threshold.)

One step is this set of actions:

   Using a normal threshold scheme, such as Shamir's Lagrange Polynomials
   a sufficient number of shareholders construct a single secret from their
   shares.  Call this M.  M is then used to update all their shares using a
   keyed hash function.

   Table 18.1 suggests      H_i = E H_i-1 (M)  XOR M

   M and every H_i-1 is destroyed.

   Now those absent from the meeting have no M value to advance
   their share, and nobody (even the other shareholders following
   a change of heart) can reproduce it for them.

   Shareholders deduct 1 from the number of steps still to be performed.