Blom's scheme
Overview
Blom's scheme is a cryptographical symmetric threshold key exchange protocol.
A trusted party gives each of the n participants a secret key and a public identifier, which enables any two participants to independently create a shared key for securely communicating with another participant. Every participant can create a shared key with any other participant, allowing secure communication to take place between any two members of the group. However, if an attacker can compromise the keys of at least k users, he can break the scheme and reconstruct every shared key. Blom's scheme is a Secret sharing.
Blom's scheme is currently used by the HDCP copy protection scheme to generate shared keys for high-definition content sources and receivers, such as HD-DVD players and high-definition televisions.
The protocol
The key exchange protocol involves a trusted party (Trent) and a group of n users. Let Alice and Bob be two users of the group.
Protocol setup
Trent chooses a random and secret matrix Dk x k over the finite field GF(p), where p is a prime number. D is required when a new user is to be added to the key sharing group.
For example, let p = 17, and D = 
.
Inserting a new participant
New users Alice and Bob want to join the key exchanging group. Trent chooses public identifiers for each of them, i.e.: k-element vectors IAlice, IBob in GF(p).
Trent then computes their private keys: gAlice = (D * IAlice), gBob = (D * IBob).
Each will use their private key to compute shared keys with other participants of the group.
Let IAlice = 
, and IBob = 
. Trent will
create Alice's and Bob's secret keys as follows:
gAlice = 
,
gBob = 
.
Computing a shared key between Alice and Bob
Now Alice and Bob wish to communicate with one another. Alice has Bob's identifier IBob and her private key gAlice.
She computes the shared key kAlice / Bob = gAlice * IBobt, where t denotes matrix transpose. Bob does the same, using his private key and her identifier.
They will each generate their shared key as follows:
kAlice / Bob = 
kBob / Alice = 
Attack resistance
In order to ensure at least k keys must be compromised before every shared key can be computed by an attacker, identifiers must be k-linearly independent: all k-sets of randomly selected user identifiers must be linearly independent. Otherwise, a group of malicious users can compute the key of any other member whose identifier is linearly dependent to theirs.
References
Handbook of applied cryptography, A. Menezes, P. van Oorschot, S. Vanstone, CRC Press, 1996
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
