Secret sharing with cheaters using multi-receiver authentication

Rui Xu, Kirill Morozov, Tsuyoshi Takagi

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


We introduce two cheater identifiable secret sharing (CISS) schemes with efficient reconstruction, tolerating t < k=2 cheaters and one robust secret sharing scheme (RSS). Our constructions, which provide public cheater identification, feature a novel application of multi- receiver authentication codes to ensure integrity of shares. The first CISS scheme, which tolerates rushing cheaters, has the share size jS j(n - t )n+t+2=ϵ n+t+2 in the general case, that can be ultimately reduced to jS j(k - t )k+t+2=ϵ k+t+2 assuming that all the t cheaters are among the k reconstructing players. The second CISS scheme, which tolerates non- rushing cheaters, has the share size jS j(n - t )2t+2=ϵ 2t+2. These two con- structions have the smallest share size among the existing CISS schemes of the same category, when the secret is a single field element. Finally, we use the tool of multi-receiver authentication to construct a robust secret sharing scheme, which updates the start-of-art against rushing adversary by reducing the share overhead by slightly more than one half. In addition, we point out that an improvement in the share size to jS j=ϵ n-(k-1)=3+1 can be achieved for a CISS tolerating t < k=3 rushing cheaters presented by Xu et al. at IWSEC 2013.

Original languageEnglish
Pages (from-to)115-125
Number of pages11
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number1
Publication statusPublished - Jan 2017

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Secret sharing with cheaters using multi-receiver authentication'. Together they form a unique fingerprint.

Cite this