Key Management - Codes: The Guide to Secrecy from Ancient to Modern Times - page 235

and

r 2 + r 3 u M ≡ y M (mod p ) , (6.2)

but not the unknown value r 1 + r 2 ( u A + u B )+ r 3 u A u B ≡ z (mod p ). Putting

this into a matrix equation we get

1 u M 0
0 1 u M
1 u A + u B u A u B

r 1
r 2
r 3

x M
y M
z

≡ (mod p ) ,

AX =

where

u 2 M + u A u B −

det( A ) ≡ ( u A + u B ) u M ≡ ( u M − u A )( u M − u B ) ≡ 0(mod p ) ,

since u M ≡ u A (mod p ) and u M ≡ u B (mod p ). Hence, there exists a solution

p , for any possible value z

( r 1 ,r 2 ,r 3 ) ∈ F p of k AB given the information

Mallory has at his disposal. Hence, Mallory obtains no information about k AB .
Although the scheme is unconditionally secure against an attack by any
individual user, it is vulnerable to a total break by more than one user acting
in concert. For instance, suppose that Mallory conspires with Eve.
Since Mallory has Equations (6.1) and (6.2) and Eve has her two similar
equations, then they have the four modular equations

∈ F

x M ≡ r 1 + r 2 u M (mod p ), y M ≡ r 2 + r 3 u M (mod p ) ,

r 2 + r 3 u E (mod p ) .
Hence, they have four equations in three unknowns from which elementary al-
gebra will yield a unique solution for r 1 ,r 2 ,r 3 .
However, the scheme can easily be made secure against any n

x E ≡ r 1 + r 2 u E (mod p ), and y E ≡

users
acting in concert by altering the choice by Trent in step 1. Trent replaces the
polynomial,

∈ N

p ( x, y )= r 1 + r 2 ( x + y )+ r 3 xy,

by

n n

r i,j x i y j (mod p ) , f x ( y ) ≡ (6.3)

i =0 j =0

for randomly chosen r i,j ∈ F p with r i,j ≡ r j,i (mod p ) for all such i, j . The

general setup (6.3) is an aspect of the full Blom protocol (see [27]). It will
however, succumbto a conspiracy by n + 1 users acting in concert in the same
fashion as above. Thus, the above polynomial can be chosen for an appropriate,
arbitrarily high, value of n .