Interesting broadcast group key management schemes

In this post, I focus on some really neat broadcast group key management schemes/protocols (BGKM). The idea behind the schemes are based on quite simple algebraic constructs, but they are very elegant.

In addition to other properties, a good GKM scheme should provide the following two properties.
1. Forward secrecy - a user who left the group should not be able to access new keys
2. Backward secrecy - a user who joined the group should not able to access old keys

In my opinion, these are two most difficult properties to satisfy in a group communication setting. In order to satisfy these two properties, it is required to initiate a rekeying operation (i.e. change the existing keys). There have been many GKM schemes proposing various way of doing rekey operation. What set them apart is the communication cost of the rekeying operation. Earlier GKM schemes had O(n) communication overhead, where n is the number of users in the group. Later, it was improved to incorporate a hierarchy and the communication overhead was reduced to O(log n). Further, these rekeying operations are not transparent to users; every time a user joins/leaves, other users need to update their keys. Can we make the communication overhead to be O(1) (i.e. independent of the number of users in the group? This is where the BGKM schemes fit.

BGKM schemes make the rekeying operation transparent to existing users at the expense of additional computational cost at the server which manages the BGKM scheme. There are three noteworthy BGKM schemes which I will go over in some details giving the key ideas in the rest of this post.

1. The secure lock (SL) approach based on the Chinese Remainder Theorem (CRT) [SE 1989]
2. The access control polynomial (ACP) approach based on special polynomials [INFOCOM 2008]
3. The access control vector (ACV) approach based on matrix null spaces [ICDE 2010]

1. The Secure Lock (SL) approach
(Slightly modified the original version)
Each user u_i is given a random secret value s_i and a unique secret number n_i at the time of joining. These n_i's are relatively prime in pairs. The server construct the following congruences and compute the common solution using the CRT and broadcast to the group whenever there is a leave or join.

x ~ r_1 (mod n_1)
x ~ r_2 (mod n_2)
...
x ~ r_n (mod n_n)

where ~ is the congruence symbol, r_i = K XOR s_i, K is the actual key. (r_i < n_i)

Then construct the common solution, using the CRT:
x ~ \sigma{i=1}{n} N/n_i * r_i * f_i (mod N)

where N = n_1 * n_2 * ... * n_n,
f_i ~ N/n_i (mod n_i).

Let the standard representative of the common solution is C.

A user u_r with the secret s_r and the public value n_r derives the key by (C mod n_r) XOR s_r. (Note that C mod n_r gives the value r_r)

Can a newly joined user u_r get its hand on old keys? No, because the old common solution did not consider the congruence x ~ r_r (mod n_r).

Can a user u_r who left the group access new keys? No, because the server removes the congruence x ~ r_r (mod n_r) from the CRT calculation.

2. The Access Control Polynomial (ACP) approach
Each user u_i is given a random secret value s_i at the time of joining. The server construct the following polynomial of order m+n and broadcast to the group whenever there is a leave or join.

f(x) = K + (x - H(s_1 || z))(x - H(s_2 || z))..(x - H(s_n || z))(x - H(a_1 || z))...(x - H(a_m || z))
where K - is the actual key, s_1,.., s_n are the random secret values given to n users, a_1,.., a_m are random fake values used to increase the entropy of f(x), z is a public random value, H is a hash function.

A user u_r with the secret s_r derives the key as f(H(s_r || z)).

Can a newly joined user u_r get its hand on old keys? No, because the old polynomials f`(x)'s do not have (x - H(s_r || z)).

Can a user u_r who left the group access new keys? No, because the server removes (x - H(s_r || z)) from the new polynomials f`(x)'s.

The scheme is quite simple. However the security of this scheme is neither formally analyzed nor proved.

3. The Access Control Vector (ACV) approach
Each user u_i is given a random secret value s_i at the time of joining. The server construct the following the matrix X of n by n + 1 and broadcast a vector created based on a random vector from the null space of X to the group whenever there is a leave or join.

X =
| 1 a_{1,1} .... a_{1,n}|
| 1 a_{2,1} .... a_{2,n}|
| ..................................|
| 1 a_{n,1} .... a_{n,n}|

where a{i,j} = H(s_i || z_i), H is a hash function, z_i's public random random values, s_i is the random secret value given to the user u_i.

The null space of such a matrix is always guranteed to be nontrivial (each row is linearly independent). Hence, there exists a non-trivial colomn vector Y such that XY = 0. The server picks a random vector Y from the null space and compute the ACV (Access Control Vector) and broadcasts.

ACV = (K, 0, ..., 0)^T + Y

A user u_r with the secret s_r derives the K by performing a dot product of ACV and KEV_r (Key Extraction Vector). A user can construct her KEV using her secret and public random z_i's as follows.

KEV_r = (1, H(s_r || z_1, ...., H(s_r || z_n))^T

Can a newly joined user u_r get its hand on old keys? No, because the vector Y in the old ACV's are not orthogonal to her KEV, dot product does not yield the key K.

Can a user u_r who left the group access new keys? No, because the server removes the corresponding row from X, now the vector Y in the new ACV's are not orthogoal to her old KEV.

The scheme is quite elegant. The security of this scheme is analyzed and proved. A downside of this approach is the computational cost at the server when the group size is large.