Blom's scheme

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 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[edit]

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[edit]

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

For example:

\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}

Inserting a new participant[edit]

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{Alice}}, I_{\mathrm{Bob}} \in GF(p).

For example:

I_{\mathrm{Alice}} = \begin{pmatrix} 3 \\ 10 \\ 11 \end{pmatrix}, I_{\mathrm{Bob}} = \begin{pmatrix} 1 \\ 3 \\ 15 \end{pmatrix}

Trent then computes their private keys:

\begin{align}
 g_{\mathrm{Alice}} &= DI_{\mathrm{Alice}}\\
 g_{\mathrm{Bob}} &= DI_{\mathrm{Bob}}
\end{align}

Using D as described above:

\begin{align}
 g_{\mathrm{Alice}} &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\begin{pmatrix} 3 \\ 10 \\ 11 \end{pmatrix} = \begin{pmatrix} 85\\136\\108\end{pmatrix}\ \mathrm{mod}\ 17 = \begin{pmatrix} 0\\0\\6\end{pmatrix}\ \\
 g_{\mathrm{Bob}} &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\begin{pmatrix} 1 \\ 3 \\ 15 \end{pmatrix} = \begin{pmatrix} 49\\135\\56\end{pmatrix}\ \mathrm{mod}\ 17 = \begin{pmatrix} 15\\16\\5\end{pmatrix}\ 
\end{align}

Each will use their private key to compute shared keys with other participants of the group.

Computing a shared key between Alice and Bob[edit]

Now Alice and Bob wish to communicate with one another. Alice has Bob's identifier \scriptstyle I_{\mathrm{Bob}} and her private key \scriptstyle g_{\mathrm{Alice}}.

She computes the shared key \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:

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}}

They will each generate their shared key as follows:

\begin{align}
 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{align}

Attack resistance[edit]

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[edit]

  1. ^ Rolf Blom. Non-public key distribution. In Proc. CRYPTO 82, pages 231–236, New York, 1983. Plenum Press
  2. ^ R. Blom, "An optimal class of symmetric key generation systems", Report LiTH-ISY-I-0641, Linköping University, 1984 [1]