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.^[1][2]

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 $\scriptstyle n$ users. Let Alice and Bob be two users of the group.

Protocol setup

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

For example:

${\displaystyle {\begin{aligned}k&=3\\p&=17\\D&={\begin{pmatrix}1&2&3\\2&4&5\\3&5&3\end{pmatrix}}\ \mathrm {mod} \ 17\end{aligned}}}$

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:

${\displaystyle I_{\mathrm {Alice} },I_{\mathrm {Bob} }\in GF^{k}(p)}$.

For example:

${\displaystyle I_{\mathrm {Alice} }={\begin{pmatrix}1\\2\\3\end{pmatrix}},I_{\mathrm {Bob} }={\begin{pmatrix}3\\2\\1\end{pmatrix}}}$

Trent then computes their private keys:

${\displaystyle {\begin{aligned}g_{\mathrm {Alice} }&=DI_{\mathrm {Alice} }\\g_{\mathrm {Bob} }&=DI_{\mathrm {Bob} }\end{aligned}}}$

Using $D$ as described above:

${\displaystyle {\begin{aligned}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}85\\136\\108\end{pmatrix}}\ \mathrm {mod} \ 17={\begin{pmatrix}14\\3\\5\end{pmatrix}}\ \\g_{\mathrm {Bob} }&={\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}{\begin{pmatrix}3\\2\\1\end{pmatrix}}={\begin{pmatrix}49\\135\\56\end{pmatrix}}\ \mathrm {mod} \ 17={\begin{pmatrix}10\\16\\5\end{pmatrix}}\ \end{aligned}}}$

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

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

${\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}DI_{\mathrm {Alice} }=k_{\mathrm {Bob/Alice} }}$

They will each generate their shared key as follows:

${\displaystyle {\begin{aligned}k_{\mathrm {Alice/Bob} }&={\begin{pmatrix}0\\0\\6\end{pmatrix}}^{t}{\begin{pmatrix}1\\3\\15\end{pmatrix}}=0\times 1+0\times 3+6\times 15=90\ \mathrm {mod} \ 17=5\\k_{\mathrm {Bob/Alice} }&={\begin{pmatrix}15\\16\\5\end{pmatrix}}^{t}{\begin{pmatrix}3\\10\\11\end{pmatrix}}=15\times 3+16\times 10+5\times 11=260\ \mathrm {mod} \ 17=5\end{aligned}}}$

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).^[3]

References

1. Blom, Rolf. Non-public key distribution. In Proc. CRYPTO 82, pages 231–236, New York, 1983. Plenum Press
2. Blom, Rolf. "An optimal class of symmetric key generation systems", Report LiTH-ISY-I-0641, Linköping University, 1984
3. Menezes, A; Paul C. van Oorschot & Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press. ISBN 0-8493-8523-7.