Blom's scheme

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 symmetric matrix D_{k 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 I_Alice, I_Bob in $GF(p)$.

Trent then computes their private keys: g_Alice = $(D*I\_\{mathrm\{Alice)$, g_Bob = $(D*I\_\{mathrm\{Bob)$.

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

Let I_Alice = , andI_Bob = .Trent will create Alice's and Bob's secret keys as follows:

g_Alice = ,

g_Bob = .

Computing a shared key between Alice and Bob

Now Alice and Bob wish to communicate with one another.Alice has Bob's identifier I_Bob and her private key g_Alice.

She computes the shared key k_{Alice / Bob} = g_Alice^t * I_Bob, 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:

k_{Alice / Bob} =

k_{Bob / Alice} =

Prove:

$k\_\{Alice\; /\; Bob\}\; =\; k\_\{Alice\; /\; Bob\}^t\; =\; (g\_\{Alice\}^t*I\_\{Bob\})^t\; =\; (I\_\{Alice\}^t\; *\; D^t\; *\; I\_\{Bob\})^t\; =\; I\_\{Bob\}^t\; *\; D\; *\; I\_\{Alice\}\; =\; k\_\{Bob/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.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 practise 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 fast).

References

cite book
author = Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone
date = 1996
title = Handbook of Applied Cryptography
publisher = CRC Press
id = ISBN 0-8493-8523-7
url = http://www.cacr.math.uwaterloo.ca/hac/