Blom's scheme is a symmetric threshold key exchange protocol in cryptography.
A trusted party gives each participant a secret key and a public identifier, which enables any two participants to independently create a shared key for communicating.
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 form of threshold secret sharing. The scheme was proposed by the Swedish cryptographer Rolf Blom in a series of articles in the early 1980s.
The key exchange protocol involves a trusted party (Trent) and a group of users. Let Alice and Bob be two users of the group.
Inserting a new participantEdit
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:
Trent then computes their private keys:
Each will use their private key to compute shared keys with other participants of the group. Trent will create Alice's and Bob's secret keys as follows:
Now Alice and Bob wish to communicate with one another. Alice has Bob's identifier and her private key .
She computes the shared key , where denotes matrix transpose. Bob does the same, using his private key and her identifier, giving the same result:
They will each generate their shared key as follows:
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. To ensure this property, the identifiers shall be preferably chosen from a MDS-Code matrix (maximum distance separable error correction code matrix). The rows of the MDS-Matrix would be the identifiers of the users. A MDS-Code matrix can be chosen in practice using the code-matrix of the Reed–Solomon error correction code (this error correction code requires only easily understandable mathematics and can be computed extremely quickly).
- Template:Cite book
- R. Blom, "An optimal class of symmetric key generation systems". Abbreviated version of the original Blom's work
- ↑ Rolf Blom. Non-public key distribution. In Proc. CRYPTO 82, pages 231–236, New York, 1983. Plenum Press
- ↑ R. Blom, "An optimal class of symmetric key generation systems", Report LiTH-ISY-I-0641, Linköping University, 1984