Blom's scheme

From Wikipedia, the free encyclopedia

1 Overview
2 The protocol
3 Attack resistance
4 References

[edit] 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.

[edit] 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.

[edit] Protocol setup

Trent chooses a random and secret symmetric matrix D_{k x 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, let p = 17, and D = $\begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\ \mathrm{mod}\ 17$ .

[edit] 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 $G F (p)$ .

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

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

Let I_Alice = $\begin{pmatrix} 3 \\ 10 \\ 11 \end{pmatrix}$ , and I_Bob = $\begin{pmatrix} 1 \\ 3 \\ 15 \end{pmatrix}$ . Trent will create Alice's and Bob's secret keys as follows:

g_Alice = $\begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix} * \begin{pmatrix} 3 \\ 10 \\ 11 \end{pmatrix} = \begin{pmatrix} 0\\0\\6\end{pmatrix}\ \mathrm{mod}\ 17$ ,

g_Bob = $\begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix} * \begin{pmatrix} 1 \\ 3 \\ 15 \end{pmatrix} = \begin{pmatrix} 15\\16\\5\end{pmatrix}\ \mathrm{mod}\ 17$ .

[edit] 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 * I_Bob^t, 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} = $\begin{pmatrix} 0\\0\\6 \end{pmatrix} * \begin{pmatrix} 1\\3\\15 \end{pmatrix}^t = 0*1 + 0*3 + 6*15 = 5\ \mathrm{mod}\ 17$

k_{Bob / Alice} = $\begin{pmatrix} 15\\16\\5 \end{pmatrix} * \begin{pmatrix} 3\\10\\11 \end{pmatrix}^t = 15*3 + 16*10 + 5*11 = 5\ \mathrm{mod}\ 17$

[edit] 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.