Secret sharing made short

[Hal <hfinney@shell.portal.com>]

I came upon a paper with this title in the 1993 Crypto conference proceedings,
by Hugo Krawczyk.  He pointed out that with the Shamir-type secret splitting
which we discuss here periodically you have considerable space expansion.
Splitting a message of M bits into N shares causes each share to itself be M
bits.  Krawczyk shows a simple system which basically has each share be only
M/N bits.  (I will ignore for simplicity the issue of providing a threshold
K<N such that any K of the N shares are sufficient to restore the message.)

He achieves this be foregoing "pure" information-theoretic secrecy in favor
of "mere" computational secrecy.  This is a reasonable tradeoff since most
implementations of Shamir sharing end up relying on computational secrecy
for their random numbers, anyway.

Krawczyk's idea, in the simple subset I am describing, is almost embarrassingly
easy.  Take your message M and encrypt it using a random IDEA or DES key.
Split the resulting cyphertext into N pieces (just carve it up) and give each
piece to a shareholder.  Take the IDEA/DES key and Shamir-split it into
N pieces and give those out as well.  (Shamir splitting for this case can
be done simply by having N-1 of the pieces be totally random, and having
the last piece be the xor of the IDEA/DES key and the N-1 random pieces.
Only by xor'ing all N pieces can the original key be recovered.)

Everyone ends up with slightly over M/N bits; they have M/N plus the size
of a DES or IDEA key.  But that is pretty close.  And unless IDEA or DES can
be broken they will have to recover all of the shares in order to recon-
struct the key and read the message.

For generalization to the K<N case you still use Shamir splitting on the
IDEA or DES key, but the message itself gets split up using an error-cor-
recting code concept so that K pieces are enough to reconstruct the message.
This requires M/K bits per share, plus the overhead for the DES/IDEA key.

This sounds like it would be a good enhancement to the Shamir splitting code
that was posted here.  The IDEA or DES module could be a source of random
bits for the Shamir splitting.  PGP's IDEA module is pretty self-contained
and has a random-number entry point.

(Oh, well, I've come this far, I might as well finish it.  The message
distribution scheme Krawczyk gives is this: split the message into K
pieces.  Treat each piece as the coefficient of a K-1 degree polynomial.
Evaluate the polynomial at X=0,...,N-1 and let the results be the shares.
Now any K of the shares will allow the polynomial to be reconstructed, and
by concatenating the coefficients we recover M.  This is similar to Shamir's
scheme but is not informationally secure and has shares of size M/K.)

Hal