Biblio

In Eurocrypt 2011, Obana proposed a (k, n) secret-sharing scheme that can identify up to ⌊((k− 2)/2)⌋ cheaters. The number of cheaters that this scheme can identify meets its upper bound. When the number of cheaters t satisfies t≤ ⌊((k− 1)/3)⌋, this scheme is extremely efficient since the size of share |Vi| can be written as |Vi| = |S|/ɛ, which almost meets its lower bound, where |S| denotes the size of secret and ε denotes the successful cheating probability; when the number of cheaters t is close to ⌊ ((k− 2)/2)⌋, the size of share is upper bounded by |Vi| = (n·(t + 1) · 2 |S|)/ɛ. A new (k, n) secret-sharing scheme capable of identifying ⌊((k − 2)/2)⌋ 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 |Vi| = (2 |S| )/ɛ, 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 |Vi | = (n · (t + 1) · 2 |S|)/ɛ 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 ⌊((k− 2)/2)⌋.