我正在解决一个(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 的情况......
非常感谢任何关于如何解决这个难题的建议!
最佳答案
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
关于python - 阈值方案分散算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42073352/