jmbhmb - 4 years ago 72

Python Question

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

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

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

The more interesting cases are

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

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!

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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**