jmbhmb - 4 years ago 72
Python Question

# Threshold scheme dispersal algorithm

I am working through a (k, n) threshold challenge that involves distributing numbered keys to a group of n individuals, such that any subset of k individuals (but not k-1) will have the necessary keys to open a lock, while using the least number of keys required to support the scheme.

I need to write a dispersal algorithm that takes (k, n) and returns the scheme as a matrix of n rows, with each row containing a set of numbered keys that combined with any other k-1 sets will have the required collection of keys. Redundancy of keys across sets is allowed.

The "trivial" cases are k = 1 and k = n:

If k = 1 then each n must have all the required keys, the least number of keys to support this scheme being 1. For example:

If k = 1 and n = 2, the scheme is:

``````[[0], [0]]
``````

If k = n then each n must have a different key, the least number of keys to support this scheme being n. For example:

If k = 4 and n = 4, the scheme is:

``````[[0], [1], [2], [3]]
``````

The more interesting cases are 1 < k < n (with space efficiency), for example:

If k = 2 and n = 3, the scheme is:

``````[[0, 1], [0, 2], [1, 2]]
``````

If k = 3 and n = 5, the scheme is:

``````[[0, 1, 2, 3, 4, 5], [0, 1, 2, 6, 7, 8], [0, 3, 4, 6, 7, 9], [1, 3, 5, 6, 8, 9], [2, 4, 5, 7, 8, 9]]
``````

I've reviewed a fair amount of material on Information Dispersal and Secret Sharing, including Rabin's IDA, Shamir's Secret Sharing, etc.

The core of these appears to be a matrix-vector product, using a transform matrix of size (n,k) multiplied by a k-element vector (the secret) producing an n-element vector (the shares to be distributed).

However, all the implementations I've reviewed are focused on actually encoding and decoding a "secret" or message and I'm struggling to generalize this to the case of simply distributing numbered keys efficiently...

Any advice on how to approach this puzzle is greatly appreciated!

Each (n-(k-1))-subset of the n people needs its own key. Let's use Python's built-in combinations support.

``````import itertools
def scheme(n, k):
keys = [[] for i in range(n)]
for j, comb in enumerate(itertools.combinations(range(n), n-(k-1))):
for i in comb:
keys[i].append(j)
return keys
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download