Blom's scheme

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. 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, they 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 [math]\displaystyle{ \scriptstyle n }[/math] users. Let Alice and Bob be two users of the group.

Protocol setup

Trent chooses a random and secret symmetric matrix [math]\displaystyle{ \scriptstyle D_{k,k} }[/math] over the finite field [math]\displaystyle{ \scriptstyle GF(p) }[/math], where p is a prime number. [math]\displaystyle{ \scriptstyle D }[/math] is required when a new user is to be added to the key sharing group.

For example:

[math]\displaystyle{ \begin{align} k &= 3\\ p &= 17\\ D &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\ \mathrm{mod}\ 17 \end{align} }[/math]

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:

[math]\displaystyle{ I_{\mathrm{Alice}}, I_{\mathrm{Bob}} \in GF^k(p) }[/math].

For example:

[math]\displaystyle{ I_{\mathrm{Alice}} = \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}, I_{\mathrm{Bob}} = \begin{pmatrix} 5 \\ 3 \\ 1 \end{pmatrix} }[/math]

Trent then computes their private keys:

[math]\displaystyle{ \begin{align} g_{\mathrm{Alice}} &= DI_{\mathrm{Alice}}\\ g_{\mathrm{Bob}} &= DI_{\mathrm{Bob}} \end{align} }[/math]

Using [math]\displaystyle{ D }[/math] as described above:

[math]\displaystyle{ \begin{align} g_{\mathrm{Alice}} &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} = \begin{pmatrix} 19\\36\\24\end{pmatrix}\ \mathrm{mod}\ 17 = \begin{pmatrix} 2\\2\\7\end{pmatrix}\ \\ g_{\mathrm{Bob}} &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\begin{pmatrix} 5 \\ 3 \\ 1 \end{pmatrix} = \begin{pmatrix} 25\\47\\36\end{pmatrix}\ \mathrm{mod}\ 17 = \begin{pmatrix} 8\\13\\2\end{pmatrix}\ \end{align} }[/math]

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 [math]\displaystyle{ \scriptstyle I_{\mathrm{Bob}} }[/math] and her private key [math]\displaystyle{ \scriptstyle g_{\mathrm{Alice}} }[/math].

She computes the shared key [math]\displaystyle{ \scriptstyle k_{\mathrm{Alice / Bob}} = g_{\mathrm{Alice}}^T I_{\mathrm{Bob}} }[/math], where [math]\displaystyle{ \scriptstyle T }[/math] denotes matrix transpose. Bob does the same, using his private key and her identifier, giving the same result:

[math]\displaystyle{ k_{\mathrm{Alice / Bob}} = k_{\mathrm{Alice / Bob}}^T = (g_{\mathrm{Alice}}^T I_{\mathrm{Bob}})^T = (I_{\mathrm{Alice}}^T D^T I_{\mathrm{Bob}})^T = I_{\mathrm{Bob}}^T D I_{\mathrm{Alice}} = k_{\mathrm{Bob / Alice}} }[/math]

They will each generate their shared key as follows:

[math]\displaystyle{ \begin{align} k_{\mathrm{Alice / Bob}} &= \begin{pmatrix} 2\\2\\7 \end{pmatrix}^T \begin{pmatrix} 5\\3\\1 \end{pmatrix} = 2 \times 5 + 2 \times 3 + 7 \times 1 = 23\ \mathrm{mod}\ 17 = 6\\ k_{\mathrm{Bob / Alice}} &= \begin{pmatrix} 8\\13\\2 \end{pmatrix}^T \begin{pmatrix} 1\\2\\3 \end{pmatrix} = 8 \times 1 + 13 \times 2 + 2 \times 3 = 40\ \mathrm{mod}\ 17 = 6 \end{align} }[/math]

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