Suvarna Garge (Editor)

Blom's scheme

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

Blom's scheme is a symmetric threshold key exchange protocol in cryptography. The scheme was proposed by the Swedish cryptographer Rolf Blom in a series of articles in the early 1980s.

Contents

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. 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.

Blom's scheme is currently used by the HDCP (Version 1.x only) 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 symmetric matrix D k , k over the finite field G F ( 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:

k = 3 p = 17 D = ( 1 2 3 2 4 5 3 5 3 )   m o d   17

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:

I A l i c e , I B o b G F k ( p ) .

For example:

I A l i c e = ( 1 2 3 ) , I B o b = ( 3 2 1 )

Trent then computes their private keys:

g A l i c e = D I A l i c e g B o b = D I B o b

Using D as described above:

g A l i c e = ( 1 6 2 6 3 8 2 8 2 ) ( 1 2 3 ) = ( 85 136 108 )   m o d   17 = ( 14 3 5 )   g B o b = ( 1 6 2 6 3 8 2 8 2 ) ( 3 2 1 ) = ( 49 135 56 )   m o d   17 = ( 10 16 5 )  

Each will use their private key to compute shared keys with other participants of the group.

Computing a shared key between Alice and Bob

Now Alice and Bob wish to communicate with one another. Alice has Bob's identifier I B o b and her private key g A l i c e .

She computes the shared key k A l i c e / B o b = g A l i c e t I B o b , where t denotes matrix transpose. Bob does the same, using his private key and her identifier, giving the same result:

k A l i c e / B o b = k A l i c e / B o b t = ( g A l i c e t I B o b ) t = ( I A l i c e t D t I B o b ) t = I B o b t D I A l i c e = k B o b / A l i c e

They will each generate their shared key as follows:

k A l i c e / B o b = ( 0 0 6 ) t ( 1 3 15 ) = 0 × 1 + 0 × 3 + 6 × 15 = 90   m o d   17 = 5 k B o b / A l i c e = ( 15 16 5 ) t ( 3 10 11 ) = 15 × 3 + 16 × 10 + 5 × 11 = 260   m o d   17 = 5

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 sets of k 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).

References

Blom's scheme Wikipedia