阈值方案分散算法

Question

我正在处理一个(k，n)阈值挑战，该挑战涉及将编号密钥分配给一组n个人，这样k个人的任何子集(但不是k-1)都将拥有打开锁所需的密钥，同时使用支持该方案所需的最少数量的密钥。

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

"琐碎"情况是k=1和k+n：

如果k=1，则每个n必须具有所有必需的密钥，支持该方案的密钥的最少数量为1。例如：

如果k=1且n=2，则方案为：

[[0], [0]]

如果k=n，则每个n必须有一个不同的密钥，支持该方案的密钥数量最少为n。例如：

如果k=4且n=4，则方案为：

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

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

如果k=2且n=3，则方案为：

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

如果k=3且n=5，则方案为：

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

我已经审查了大量关于信息分散和秘密共享的材料，包括Rabin的IDA、Shamir的秘密共享等。

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

然而，我审查过的所有实现都集中在实际编码和解码"秘密"或消息上，我很难将其推广到简单有效地分发编号密钥的情况。。。

任何关于如何处理这个谜题的建议都将不胜感激！

Answer 1

n个人的每个(n-(k-1))子集都需要自己的密钥。让我们使用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