(k, n)しきい値法における多数決を用いた不正検出方式とその性能評価

摘要

秘密分散法のひとつである（k，n)しきい値法では，高々k-1次の生成多項式を用いることで秘密をn個のシェアに分散させ参加者に配布し，そのうち任意のk個のシェアが集まれば秘密を復元することができる.しかし，k個の中に不正者によって改ざんされたシェアが存在してしまう場合は正しい復元に失敗してしまう.この問題の解決策として本稿では不正者の存在下でも正しい復元が行える手法として，Hara-Linが提案した手法の改善策を提案する.提案手法ではn個からfc個を選ぶすべての組み合わせを考え，そこから秘密だけでなく生成多項式の全ての係数についても復元を行い，その結果に対して多数決を適用させることで正しい復元結果を決定する.このとき正しい復元が行える参加者と不正者の人数に関する条件の考察を行い，さらに復元に失敗してしまう場合について確率的な評価を行う.%The (k, n)-threshold scheme is a kind of secret sharing scheme. In this scheme, a secret is encoded to n shares and distributed to n participants by a dealer. If any k participants gather, they will be able to reconstruct the original secret correctly from their k shares. Shamir's scheme is one of the most fundamental (k, n)-threshold schemes using a random polynomial of degree at most k -1.However, Shamir's scheme always fails to reconstruct the secret in the reconstruction phase if some of k participants are not honest. In order to raise reliability of Shamir's scheme, we propose an improved version of the reconstruction scheme proposed by Harn and Lin. In this scheme, the majority rule is introduced into the reconstruction phase, where we compute all the coefficients obtained from every combination of k shares. We obtain a sufficient condition on the number of dishonest participants under which the secret is correctly reconstructed with probability1.In addition, we evaluate the probability such that the proposed scheme fails to reconstruct the secret in certain cases.