Antisymmetrizer

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

Protocol setup

Trent chooses a random and secret symmetric matrix $D_{k,k}$ over the finite field $GF(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:

$\begin{array}{rl}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:

$I_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}},I_{\mathrm{B}\mathrm{o}\mathrm{b}}\in GF(p)$.

For example:

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

Trent then computes their private keys:

$\begin{array}{rl}{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 $D$ as described above:

$\begin{array}{rl}{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}3\\ 10\\ 11\end{array}\right)=\left(\begin{array}{c}85\\ 136\\ 108\end{array}\right)\mathrm{m}\mathrm{o}\mathrm{d}17=\left(\begin{array}{c}0\\ 0\\ 6\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}1\\ 3\\ 15\end{array}\right)=\left(\begin{array}{c}49\\ 135\\ 56\end{array}\right)\mathrm{m}\mathrm{o}\mathrm{d}17=\left(\begin{array}{c}15\\ 16\\ 5\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 $I_{\mathrm{B}\mathrm{o}\mathrm{b}}$ and her private key $g_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}$.

She computes the shared key $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 $t$ denotes matrix transpose. Bob does the same, using his private key and her identifier, giving the same result:

$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:

$\begin{array}{rl}{k}_{\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}/\mathrm{B}\mathrm{o}\mathrm{b}}& ={\left(\begin{array}{c}0\\ 0\\ 6\end{array}\right)}^t\left(\begin{array}{c}1\\ 3\\ 15\end{array}\right)=0\times 1+0\times 3+6\times 15=90\mathrm{m}\mathrm{o}\mathrm{d}17=5\\ k_{\mathrm{B}\mathrm{o}\mathrm{b}/\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}}& ={\left(\begin{array}{c}15\\ 16\\ 5\end{array}\right)}^t\left(\begin{array}{c}3\\ 10\\ 11\end{array}\right)=15\times 3+16\times 10+5\times 11=260\mathrm{m}\mathrm{o}\mathrm{d}17=5\end{array}$

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

References

• 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
  
  My blog: http://www.primaboinca.com/view_profile.php?userid=5889534