Efficient t-cheater identifiable (k, n) secret-sharing scheme for t <= left perpendicular((k-2)/2)right perpendicular
In Eurocrypt 2011, Obana proposed a (k, n) secret-sharing scheme that can identify up to left perpendicular(k - 2)/2)left perpendicular cheaters. The number of cheaters that this scheme can identify meets its upper bound. When the number of cheaters t satisfies t <= left perpendicular((k - 1)/3)right perpendicular, this scheme is extremely efficient since the size of share |V-i| can be written as |V-i| = |S|/epsilon, which almost meets its lower bound, where |S| denotes the size of secret and epsilon denotes the successful cheating probability; when the number of cheaters t is close to left perpendicular((k - 2)/2)right perpendicular, the size of share is upper bounded by |V-i| = (n.(t + 1) . 2(3t - 1)|S|)/epsilon. A new (k, n) secret-sharing scheme capable of identifying left perpendicular(k - 2)/2)right perpendicular cheaters is presented in this study. Considering the general case that k shareholders are involved in secret reconstruction, the size of share of the proposed scheme is |V-i| = (2(k - 1)|V| )/epsilon, which is independent of the parameters t and n. On the other hand, the size of share in Obana's scheme can be rewritten as |V-i | = (n . (t + 1) . 2(k - 1)|S|)/epsilon under the same condition. With respect to the size of share, the proposed scheme is more efficient than previous one when the number of cheaters t is close to left perpendicular((k - 2)/2)right perpendicular.
(k n) secret-sharing scheme cheating probability probability secret reconstruction obana's scheme public key cryptography k-shakeholders