Paper 2018/837

Constructing Ideal Secret Sharing Schemes based on Chinese Remainder Theorem

Yu Ning, Fuyou Miao, Wenchao Huang, Keju Meng, Yan Xiong, and Xingfu Wang

Abstract

Since $(t,n)$-threshold secret sharing (SS) was initially proposed by Shamir and Blakley separately in 1979, it has been widely used in many aspects. Later on, Asmuth and Bloom presented a $(t,n)$-threshold SS scheme based on the Chinese Remainder Theorem(CRT) for integers in 1983. However, compared with the most popular Shamir's $(t,n)$-threshold SS scheme, existing CRT based schemes have a lower information rate, moreover, they are harder to construct. To overcome these shortcomings of the CRT based scheme, 1) we first propose a generalized $(t,n)$-threshold SS scheme based on the CRT for the polynomial ring over a finite field. We show that our scheme is ideal, i.e., it is perfect in security and has the information rate 1. By comparison, we show that our scheme has a better information rate and is easier to construct compared with existing threshold SS schemes based on the CRT for integers. 2) We show that Shamir's scheme, which is based on the Lagrange interpolation polynomial, is a special case of our scheme. Therefore, we establish the connection among threshold schemes based on the Lagrange interpolation, schemes based on the CRT for integers and our scheme. 3) As a natural extension of our threshold scheme, we present a weighted threshold SS scheme based on the CRT for polynomial rings, which inherits the above advantages of our threshold scheme over existing weighted schemes based on the CRT for integers.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2018
Keywords
Threshold Secret SharingChinese Remainder TheoremPolynomial Ring
Contact author(s)
sirning @ mail ustc edu cn
mfy @ ustc edu cn
History
2018-09-06: received
Short URL
https://ia.cr/2018/837
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/837,
      author = {Yu Ning and Fuyou Miao and Wenchao Huang and Keju Meng and Yan Xiong and Xingfu Wang},
      title = {Constructing Ideal Secret Sharing Schemes based on Chinese Remainder Theorem},
      howpublished = {Cryptology ePrint Archive, Paper 2018/837},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/837}},
      url = {https://eprint.iacr.org/2018/837}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.