Cheating identifiable secret sharing scheme using symmetric bivariate polynomial

In (k, n) secret sharing scheme, any m out of the n users (m ≥ k) can reconstruct the secret and any less than k users cannot get any information on the secret. However, some cheaters can submit fake shares to fool other honest users during secret reconstruction. Cheating identification is an important technical to prevent such cheating behavior. In this paper, we consider cheating problem in bivariate polynomial based secret sharing scheme, and propose two cheating identification algorithms respectively. The first algorithm can identify cheaters by the m users who participate in secret reconstruction; the second algorithm can achieves stronger capability of cheater identification with the collaboration of the rest n−m users who are not involved in secret reconstruction. In our scheme, the cheating identification is only based on the symmetry property of bivariate polynomial and linearity of interpolated polynomial. Both the two algorithms are efficient with respect of cheater identification capabilities.