Using key threshold schemes

The issue was raised as to whether the XML Encryption spec would support
a threshold-based key sharing scheme.  In developing the XML Encryption
specification, it was decided early on that such schemes were outside
the scope of the WG effort. But since there is some continuing interest,
I've tried to indicate how they could be accomodated.

A threshold-based key distribution scheme is one which employs an
algorithm to decompose the secret key S into 'n' distinct fragments Si
where i=1 to n. It then allows the secret value to be reconstituted from
'm' fragments, where m is a known quantity less than n. Possession of
m-1 or fewer fragments gives one little or no information about the
secret value. There are a number of known schemes for doing this, such
as those by Shamir and Blakley.

If we wanted to employ such an algorithm, there are several ways it
could be used with the XML Encryption Syntax. In all cases, we assume
one has created encrypted XML (i.e., an EncryptedData element) and
wishes to use a threshold scheme for communicating the decryption key to
the recipients.

1. The originator securely distributes the secret fragments to a number
of trusted distribution sites or trusted secret fragment holders. They
need to communicate the identity of these entities to the encrypted data
recipient. If the recipient can convince at least 'm' of these entities
to supply their fragment, the data can be decrypted.

This amounts to the problem of communicating references to at least 'm'
entities. I believe the best approach to this problem is to leverage the
ds:RetrievalMethod child of ds:KeyInfo. The structure would look like:

<KeyInfo>
   <RetrievalMethod URI="http://xyz" Type="http://shamir-threshold"/>
   <RetrievalMethod URI="http://lmn" Type="http://shamir-threshold"/>
       ....
   <RetrievalMethod URI="http://abc" Type="http://shamir-threshold"/>
</KeyInfo>
where the Type attribute is used to indicate the threshold scheme.

Alternately, one could encode these fragment references within the
xenc:EncryptionMethod element using some private scheme. But, I find
this less desirable as it places key information in a location counter
to the general design principles of XML Encryption. In either case, one
could indicate in the EncryptionMethod's Algorithm attribute that a key
threshold scheme is being used.

2. The originator distributes 'l' secret fragments to potential
recipients using some convenient mechanism such as email or a Web site.
These can be communicated in the clear since they don't help a hostile
party determine the actual secret value.

They now need to communicate a small number of fragments 'k' with the
EncryptedData such that l+k = m. I would suggest using the XML
Encryption EncryptedKey element for this purpose. Each fragment would be
secured by encrypting it to the recipient using, for example, RSA
encryption with the recipient public key. These EncryptedKey elements
can then be included under the EncryptedData's KeyInfo element, or
placed elsewhere and referenced using RetrievalMethod elements as shown
in #1.

To indicate a linkage between each key fragment, including those
pre-distributed. One could associate a common CarriedKeyName with each.
The KeyName child of KeyInfo would be used to indicate which set of
secret fragments to use in decrypting the data.

I can imagine some variations on the above scenarios, but they are
solved using the same general approaches. Of course, one could also
distribute 'm' fragments out-of-band from the EncryptedData, in which
case we just need a way to tell the recipient which ones to use. KeyName
should suffice for this. One other degenerate case is that of wanting to
send 'm' EncryptedKey fragments along with the EncryptedData. In this
case, one could simple send the complete key value in an EncryptedKey
with equivalent security. 

There are some more eleborate sharing schemes one can imagine.  For
example, a system where the key value can be retireved from http://Alice
or by assembling 'm' fragments from a set of sites. These might not be
adequately handling using RetrievalMethod and/or EncryptedKey as
discussed above.  In this case, one can define an XML element structure
to communicate the correct semantics and include with KeyInfo using the
defined extensibility mechanism.

Blair