How to Verify the Threshold t of Shamir's (t, n)-Threshold Scheme

概要

論文の詳細を見る
In the Shamir (t, n)-threshold scheme, the dealer constructs a random polynomial f(x) ∈ GF(p)[x] of degree at most t-1 in which the constant term is the secret K ∈ GF(p). However, if the chosen polynomial f(x) is of degree less than t-1, then a conspiracy of any t-1 participants can reconstruct the secret K;on the other hand, if the degree of f(x) is greater than t-1, then even t participants can not reconstruct the secret K properly. To prevent these from happening, the degree of the polynomial f(x) should be exactly equal to t-1 if the dealer claimed that the threshold of this scheme is t. There also should be some ways for participants to verify whether the threshold is exactly t or not. A few known verifiable threshold schemes provide such ability but the securities of these schemes are based on some cryptographic assumptions. The purpose of this paper is to propose some threshold-verification protocols for the Shamir (t, n)-threshold scheme from the viewpoint of unconditional security.