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, 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.[3]
The key exchange protocol involves a trusted party (Trent) and a group of
\scriptstylen
\scriptstyleDk,k
\scriptstyleGF(p)
\scriptstyleD
For example:
\begin{align} k&=3\\ p&=17\\ D&=\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix} mod 17 \end{align}
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:
IAlice,IBob\inGFk(p)
For example:
IAlice=\begin{pmatrix}1\ 2\ 3\end{pmatrix},IBob=\begin{pmatrix}5\ 3\ 1\end{pmatrix}
Trent then computes their private keys:
\begin{align} gAlice&=DIAlice\\ gBob&=DIBob\end{align}
Using
D
\begin{align} gAlice&=\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} mod 17=\begin{pmatrix}2\\2\\7\end{pmatrix} \\ gBob&=\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} mod 17=\begin{pmatrix}8\\13\\2\end{pmatrix} \end{align}
Each will use their private key to compute shared keys with other participants of the group.
Now Alice and Bob wish to communicate with one another. Alice has Bob's identifier
\scriptstyleIBob
\scriptstylegAlice
She computes the shared key
\scriptstylekAlice/Bob=
| T | |
| g | |
| Alice |
IBob
\scriptstyleT
kAlice/Bob=
| T | |
| k | |
| Alice/Bob |
=
| T | |
| (g | |
| Alice |
IBob)T=
| T | |
| (I | |
| Alice |
DTIBob)T=
| T | |
| I | |
| Bob |
DIAlice=kBob/Alice
They will each generate their shared key as follows:
\begin{align} kAlice/Bob&=\begin{pmatrix}2\\2\\7\end{pmatrix}T\begin{pmatrix}5\\3\\1\end{pmatrix}=2 x 5+2 x 3+7 x 1=23 mod 17=6\\ kBob/Alice&=\begin{pmatrix}8\\13\\2\end{pmatrix}T\begin{pmatrix}1\\2\\3\end{pmatrix}=8 x 1+13 x 2+2 x 3=40 mod 17=6 \end{align}
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).[4]