python - 阈值方案分散算法

Question

我正在解决一个(k, n) threshold 挑战，该挑战涉及将编号 key 分配给一组 n 个个体，这样 k 个个体的任何子集(但不是 k-1)将具有开锁所需的 key ，同时使用支持该方案所需的最少数量的 key 。

我需要编写一个分散算法，它采用 (k, n) 并将方案作为 n 行的矩阵返回，每行包含一组带编号的键，这些键与任何其他 k-1 组组合将具有所需的 key 的集合。允许跨集合的 key 冗余。

"trivial"情况是k = 1 和k = n:

如果k = 1 则每个n 必须具有所有必需的键，支持此方案的最少键数为1。例如:

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

[[0], [0]]

如果k = n 那么每个n 必须有一个不同的 key ，支持这个方案的最少 key 数是n。例如:

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

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

比较有趣的情况是1 < k < n(具有空间效率)，例如:

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

我查阅了大量有关信息传播 和 Secret Sharing 的资料，包括Rabin的IDA、Shamir的Secret Sharing等

这些的核心似乎是矩阵向量乘积，使用大小为 (n,k) 的变换矩阵乘以 k 元素向量( secret )产生 n 元素向量(要分配的份额).

但是，我审查过的所有实现都集中在实际编码和解码“ secret ”或消息上，我正在努力将其推广到简单有效地分发编号 key 的情况......

非常感谢任何关于如何解决这个难题的建议!

Answer 1

n 个人的每个 (n-(k-1))- 子集都需要自己的 key 。让我们使用 Python 的内置组合支持。

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