Blom's scheme is a symmetric threshold
key exchange
Key exchange (also key establishment) is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm.
If the sender and receiver wish to exchange encrypted messages, each ...
protocol in
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
. 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, 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
High-bandwidth Digital Content Protection (HDCP) is a form of digital copy protection developed by Intel Corporation to prevent copying of digital audio and video content as it travels across connections. Types of connections include DisplayPort ...
(Version 1.x only) copy protection scheme to generate shared keys for high-definition content sources and receivers, such as
HD DVD
HD DVD (short for High Definition Digital Versatile Disc) is an obsolete high-density optical disc format for storing data and playback of high-definition video. Supported principally by Toshiba, HD DVD was envisioned to be the successor to the ...
players and
high-definition television
High-definition television (HD or HDTV) describes a television system which provides a substantially higher image resolution than the previous generation of technologies. The term has been used since 1936; in more recent times, it refers to the g ...
s.
The protocol
The key exchange protocol involves a trusted party (Trent) and a group of
users. Let
Alice and Bob
Alice and Bob are fictional characters commonly used as placeholders in discussions about cryptographic systems and protocols, and in other science and engineering literature where there are several participants in a thought experiment. The Al ...
be two users of the group.
Protocol setup
Trent chooses a random and secret
symmetric matrix
In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally,
Because equal matrices have equal dimensions, only square matrices can be symmetric.
The entries of a symmetric matrix are symmetric with ...
over the
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
, where p is a prime number.
is required when a new user is to be added to the key sharing group.
For example:
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:
.
For example:
Trent then computes their private keys:
Using
as described above:
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
and her private key
.
She computes the shared key
, where
denotes
matrix transpose
In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations).
The tr ...
. Bob does the same, using his private key and her identifier, giving the same result:
They will each generate their shared key as follows:
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
{{Reflist
Secret sharing
Key management