jmbhmb 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!

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