Blom's scheme

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

Protocol setup

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

For example:

${\displaystyle \begin{array}{cc}k& =3\\ p& =17\\ D& =\left(\begin{array}{ccc}1& 6& 2\\ 6& 3& 8\\ 2& 8& 2\end{array}\right)\mathrm{m}\mathrm{o}\mathrm{d}17\end{array}}$

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{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}},I_{\mathrm{B}\mathrm{o}\mathrm{b}}\in G{F}^k(p)}$.

For example:

${\displaystyle I_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}=\left(\begin{array}{c}1\\ 2\\ 3\end{array}\right),I_{\mathrm{B}\mathrm{o}\mathrm{b}}=\left(\begin{array}{c}5\\ 3\\ 1\end{array}\right)}$

Trent then computes their private keys:

${\displaystyle \begin{array}{cc}{g}_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}& =D{I}_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}\\ g_{\mathrm{B}\mathrm{o}\mathrm{b}}& =D{I}_{\mathrm{B}\mathrm{o}\mathrm{b}}\end{array}}$

Using ${\displaystyle D}$ as described above:

${\displaystyle \begin{array}{cc}{g}_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}& =\left(\begin{array}{ccc}1& 6& 2\\ 6& 3& 8\\ 2& 8& 2\end{array}\right)\left(\begin{array}{c}1\\ 2\\ 3\end{array}\right)=\left(\begin{array}{c}19\\ 36\\ 24\end{array}\right)\mathrm{m}\mathrm{o}\mathrm{d}17=\left(\begin{array}{c}2\\ 2\\ 7\end{array}\right)\\ g_{\mathrm{B}\mathrm{o}\mathrm{b}}& =\left(\begin{array}{ccc}1& 6& 2\\ 6& 3& 8\\ 2& 8& 2\end{array}\right)\left(\begin{array}{c}5\\ 3\\ 1\end{array}\right)=\left(\begin{array}{c}25\\ 47\\ 36\end{array}\right)\mathrm{m}\mathrm{o}\mathrm{d}17=\left(\begin{array}{c}8\\ 13\\ 2\end{array}\right)\end{array}}$

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 I_{\mathrm{B}\mathrm{o}\mathrm{b}}}$ and her private key ${\displaystyle g_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}}$.

She computes the shared key ${\displaystyle k_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}/\mathrm{B}\mathrm{o}\mathrm{b}}=g_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}^T{I}_{\mathrm{B}\mathrm{o}\mathrm{b}}}$, where ${\displaystyle T}$ denotes matrix transpose. Bob does the same, using his private key and her identifier, giving the same result:

${\displaystyle k_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}/\mathrm{B}\mathrm{o}\mathrm{b}}=k_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}/\mathrm{B}\mathrm{o}\mathrm{b}}^T=(g_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}^T{I}_{\mathrm{B}\mathrm{o}\mathrm{b}}{)}^T=(I_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}^T{D}^T{I}_{\mathrm{B}\mathrm{o}\mathrm{b}}{)}^T=I_{\mathrm{B}\mathrm{o}\mathrm{b}}^{T}D{I}_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}=k_{\mathrm{B}\mathrm{o}\mathrm{b}/\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}}$

They will each generate their shared key as follows:

${\displaystyle \begin{array}{cc}{k}_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}/\mathrm{B}\mathrm{o}\mathrm{b}}& ={\left(\begin{array}{c}2\\ 2\\ 7\end{array}\right)}^T\left(\begin{array}{c}5\\ 3\\ 1\end{array}\right)=2\times 5+2\times 3+7\times 1=23\mathrm{m}\mathrm{o}\mathrm{d}17=6\\ k_{\mathrm{B}\mathrm{o}\mathrm{b}/\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}& ={\left(\begin{array}{c}8\\ 13\\ 2\end{array}\right)}^T\left(\begin{array}{c}1\\ 2\\ 3\end{array}\right)=8\times 1+13\times 2+2\times 3=40\mathrm{m}\mathrm{o}\mathrm{d}17=6\end{array}}$