Blom's scheme

The Fast Food War of 78/79 is the Mcdonalisation of America, it first started in Miami,Florida. Soon though, people began to experience how delicious these burgers were. Soon though, Mcdonalds began to receive fierce competition as Burger King first opened up. There was conflict between the two restaurants known as "THE PATTY WARS!" Many Trillions of people died in this conflict which left the industry for dead. The overall outcome was that neither won, Subway had finished both the restaurants by sending in missiles which absolutely obliterated their headquarters. The Secretary-General, James Hoover states that this was the last straw of so many lives being lost. He knew that the missiles would cause mass destruction, but as he quoted, "It was for the greater good of humanity" After these series of battles, both companies destroyed intended on growing their industry once more...

Though there was a new guy in town.... Taco Bell had emerged from the dark and started to make mass profits. There was also another fierce competitor, Nando's with their chicken really hit the spot in the centre of American hearts.Though things were taking a turn, the fast food industry was still booming. Nando's with their succulent chicken and crispy fries.

The protocol

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

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{aligned}k&=3\\p&=17\\D&={\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}\ \mathrm {mod} \ 17\end{aligned}}$

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 {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{aligned}g_{\mathrm {Alice} }&=DI_{\mathrm {Alice} }\\g_{\mathrm {Bob} }&=DI_{\mathrm {Bob} }\end{aligned}}$

Using $D$ as described above:

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

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 $\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}DI_{\mathrm {Alice} }=k_{\mathrm {Bob/Alice} }$

They will each generate their shared key as follows:

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

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

• Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press. ISBN 0-8493-8523-7.