防欺骗行为的密钥共享方案

在门限方案中，作为信任中心TA和持有份额的秘密共享者A_i都有可能不诚实，以至于会发生欺骗行为。如今，出现了一些对（t，n）门限方案的改进方案，重点在于研究如何检测或者防止这些欺骗行为的出现。

1.防止信任中心TA的欺骗行为

对于TA的欺骗行为，一种情况是TA选定了一个共享密钥，却根据另一个假共享密钥来产生共享份额给共享者。这种行为只需要求TA生成并公布一个对应于真实秘密的承诺值来证明他的诚实性，即可阻止TA的欺骗。

TA欺骗的另一种可能是他对外公开的门限值是t，而实际上选用的g（x）却不是t-1次的多项式（这里以Shamir门限方案为例）。对于这个问题，现在有一种方法可以使共享者确信TA所选的多项式g（x）至多是t-1次的，该方法如下：

1）TA利用g（x）产生所需数量的秘密份额，分发给共享者。

2）TA另选大量t-1次多项式，比如说100个，h₁（x），h₂（x），…，h₁₀₀（x），并利用它们各自生成一套秘密份额，也分别分发给共享者。

3）全体共享者合作任选50个h_i（x），并根据相应的秘密份额将它们重建出来。如果重建的这50个多项式都是t-1次的，则几乎可以确信另50个未重建的h_i（x）也是t-1次的。

4）全体共享者合作，利用剩下的50个h_i（x）和g（x）对应的秘密份额，一一重建h_i（x）+g（x），如果所有重建出来的h_i（x）+g（x）都是t-1次的，则几乎可以确信g（x）至多是t-1次的。

这个方案是Benaloh在1986年提出来的，它只能使每一个共享者确信TA选用的g（x）至多是t-1次的，但不能保证g（x）正好是t-1次的。如果g（x）的次数低于t-1，则少于t个秘密份额也能恢复共享密钥，这将成为潜在的安全漏洞。

2.防止共享者的欺骗行为(www.xing528.com)

共享者可能为了达到各种不同的目的并采取不同的方式进行欺骗，但总体上可以从两个方面识别欺骗者的企图：一是为了阻止共享密钥的正常恢复；二是为了得到其他共享者的份额，从而使自己能够独自重建共享密钥。一般来讲，欺骗者想要实现他的企图，必须提供一个虚假的秘密份额。因此，如果能对共享者出示的份额进行有效地真实性检测，则可识别出谁是欺骗者，然后立即终止同欺骗者的合作，从而阻止欺骗行为的发生。

下面介绍一种能够公平恢复共享密钥的方案，它能使欺骗者成功获得共享密钥的概率降到很低。

这个方案是Martin Tompa和Heather Woll在1988年提出来的，可以被看做是对Shamir门限方案的改进。在这个方案中，信任中心TA随机选取一个数值m＜p，并将需要保护的共享密钥k≠m隐藏于一个整数列D₁，D₂，…，D_L中，其中对某个随机的i，D_i=k，而对任何j≠i，D_j=m。然后，TA对外公布m，并对数列中的每一个元素产生秘密份额及所有其他必需的参数，分发给全体共享者。

当有t个共享者希望重建共享密钥时，他们交换各自掌握的秘密份额及相关参数，依次重建D₁，D₂，…，D_L，直到发现某个D_i≠m。此时，如果D_i不符合事先约定的某个条件，比如应满足D_i＜p等，则可以肯定有骗子出现了，因此需要立即终止协议的运行，以阻止欺骗者得逞。如果D_i没有明显的差错，那么它可能就是共享密钥k，也可能不是。对于前者则可以确定没有骗子存在；若是后者，则表明有人提供了假的份额，但在这种情况下欺骗者还不能得到共享密钥。

但Martin Tompa和Heather Woll提出的方案有两种情况可能使欺骗者有机会获得成功。第一种情况是如果欺骗者有能力确保每一次重建密钥时他都是最后一个提交份额的，那么他可以伺机决定出示真的份额还是伪造的份额；另一种情况是如果他能够准确地预测出共享密钥k在哪一轮被重构出来的，那么欺骗者就可在共享密钥k所在的那一轮提交一个伪造的秘密份额。

如果系统具有同时同步能力，所有参与密钥重构操作的共享者都必须同时提交自己的秘密份额，那么上述第一种情况下的欺骗就不存在了；另一方面，由于共享密钥k随机隐藏于数列D₁，D₂，…，D_L之中，预测k的位置并不容易，只有1/L的概率能够猜对k的位置。因此，如果系统能够同时同步，那么欺骗者成功的机会只有1/L，如果L取得足够大，这个概率是很低的。

1995年，Hung-Yu Lin和Lein Harn进一步改进了上面的方案，提出一种不需要同时同步的秘密共享方案，使参加密钥重构者可以逐个提交各自的秘密份额，而不会给投机者留下欺骗的机会。其方法如下：

信任中心TA将共享密钥k随机地隐藏于一个整数列D₁，D₂，…，D_j-1，k，m，D_j+2，…，D_L中，则有D_j=k，D_j+1=m。TA将m对外公开，一一产生数列中的元素并对全体共享者分发秘密份额，在密钥恢复时，依次重构数列中每一个元素。设想欺骗者仍然是在每一轮的最后提交份额，从而优先导出每一轮的共享密钥。当他在某一轮导出k时，还不能确定此时得到的就是真正的共享密钥k，接着他又导出了m，现在确信上一轮得到的就是共享密钥k，但此时所有参与者都已经知道k了，欺骗者并没有将k独享。在这个改进的方案中，欺骗者成功的概率仍然是1/L，但系统不需要具备同时同步能力。