Secret Sharing

[Phil Sutter]

Hello again,

some time has passed since I wrote to this list for the first time,
which I used to get a better idea of what exactly I will do. Thanks a
lot so far for your hints and questions, they helped me a lot
understanding how GnuPG works internally and which caveats there are.

The plan is as follows:

using an implementation of Shamir's (t,w)-threshold scheme I want to
share the passphrase to a secret key. At least for now the algorithm
will operate in GF(p).

So the actual passphrase is just a randomly chosen number in range
[0,p[. Each share will (theoretically) consist of two numbers in the
same range (i.e. a point of the secret function).

Identifying participants by their GPG key ID allows securing each share
by encrypting it.

For recombining I want to implement a daemon like gpg-agent
communicating with GnuPG via libassuan. The two methods for recombining
supported by PGP, either collecting the shares via network or locally
(providing a passphrase to unlock the share) should be a good starting
point.

Setup could maybe also be done externally. I think of the process as
follows:
1. read threshold t and participants' Key IDs P(i) from user
2. get a prime p
3. generate the random coefficients C(i) to a secret function of degree t-1
4. generate a new GPG key using C(0) as passphrase
5. for each P(i) retrieve a point on the secret function and encrypt the
   data using P(i)'s public key
6. forget C(i) and send the shares to the participants.

Some things I'm still not quite sure of:
* is it good or even possible to have some metadata about the secret
  sharing on the combiner's side (i.e. where the shared secret key
  resides)? The setup process described above requires at least p to be
  either made public, included in each share or be remembered by the
  combiner. Also having each share's abscissa being public or at least
  known to the combiner could be a good thing.
* How to establish a secure connection between the combiner and the
  participants? Are there any implementations using GPG keys? (An
  additional key for the combiner would be necessary.)
* A simple implementation of Shamir's threshold scheme would give each
  participant P(i) the secret function's value f(i) as share. Using GPG
  key IDs this could also work here, assumed that key IDs are unique, of
  course. Alternatively a combination of key ID and fingerprint could be
  used.
* Binary compatibility to PGP's implementation would be really great,
  but this requires deeper investigations of their protocol and binary
  format and I doubt they will let me look at their code (especially for
  this purpose ;).

Ok, that's it for now. What do you think, is this approach worth a try
or is there a fundamental problem I didn't recognise yet? Of course I
also appreciate any other kind of feedback to this email. :)

Greetings, Phil
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
URL: </pipermail/attachments/20080525/7689ef96/attachment.pgp>