Efficient (n, t, n) secret sharing schemes

https://doi.org/10.1016/j.jss.2012.01.027Get rights and content

Abstract

Recently, Harn and Lin introduced a notion of strong t-consistency of a (t, n) secret sharing scheme and proposed a strong (n, t, n) verifiable secret sharing (VSS). In this paper, we propose a strong (n, t, n) VSS which is more efficient than Harn and Lin's VSS. Using the same approach, we propose a (n, t, n) multi-secret sharing scheme (MSS) to allow shareholders to share n  t + 1 secrets. Also, the proposed (n, t, n) MSS can be modified to include the verifiable feature. All proposed schemes are unconditionally secure and are based on Shamir's (t, n) secret sharing scheme.

Highlights

► We propose an efficient (n, t, n)-VSS. ► We propose a (n, t, n)-MSS. ► We propose a (n, t, n)-VMSS. ► All our (n, t, n) SS are unconditionally secure.

Introduction

Secret sharing (SS) is one of main research topics in modern cryptography and has been studied extensively in the literature. Blakley (1979) and Shamir (1979) independently proposed SS solutions for safeguarding cryptographic keys. In a (t, n) SS, the dealer divides the secret into n shares and distributes shares to n shareholders in such a way that any t or more than t shares can reconstruct this secret; but any t  1 or fewer than t  1 shares cannot obtain any information of the secret.

There are vast research papers on this subject. Recently, Harn and Lin (2010) introduced a notion of strong t-consistency of a (t, n) SS and proposed a strong verifiable secret sharing (VSS) scheme. In this paper, we propose an efficient strong (n, t, n) VSS which is more efficient than Harn and Lin's VSS (Harn and Lin, 2010). In addition, we propose a (n, t, n) multi-secret sharing scheme (MSS) to allow shareholders to share n  t + 1 secrets. A verifiable (n, t, n) MSS (VMSS), which is based on the proposed (n, t, n) MSS, is also introduced. All proposed schemes are unconditionally secure and are simple variation of original Shamir's (t, n) SS scheme.

In Shamir's (t, n) SS scheme, it assumes that a mutually trusted dealer divides the secret into n shares and distributes each share to corresponding shareholder secretly. Chor et al. (1985) presented a notion of verifiable secret sharing (VSS). The property of verifiability enables shareholders to verify that their shares are consistent. VSS has become a fundamental tool in distributed cryptographic researches, including secure multiparty computation (MPC) (Beerliova and Hirt, 2008, Cramer et al., 2000) and Byzantine agreement (BA) protocol (Cachin et al., 2005). The security of VSSs can be classified into two types that are either computational security (Feldman, 1987) or unconditional security (Nikov and Nikova, 2005, Pedersen, 1992). For example, the security of Feldman's VSS (Feldman, 1987) is based on the hardness of solving the discrete logarithm, and the security of Pederson's VSS (Pedersen, 1992) and Nikov and Nikova's VSS (Nikov and Nikova, 2005) are unconditional security.

In Shamir's (t, n) SS (Shamir, 1979), a mutually trusted dealer is responsible to generate shares and distribute each share to corresponding shareholder secretly. Ingemarsson and Simmons (1991) introduced a new type of SS without the assistance of a mutually trusted dealer. The basic idea of this type of SS is that each shareholder also acts as a dealer to select a sub-secret and generate shares for other shareholders. The master secret is the summation of all sub-secrets. However, there is one potential problem in their design. That is, the number of shares kept by each shareholder is proportional to the number of shareholders in the scheme. Therefore, the storage and management of shares are very complicated. Pedersen (1991) proposed a solution to overcome the previous mentioned problem. Harn and Lin (2010) denoted Pedersen's approach as a (n, t, n) SS in which the first parameter, n refers to the number of dealers, the second parameter, t refers to the threshold, and the third parameter, n refers to the number of shareholders, in the SS. Harn and Lin also introduced a new notion of strong t-consistency of shares and proposed a strong (n, t, n) VSS.

In the (t, n) SS, the secret is protected by multiple shareholders; however, it requires very large data expansion (i.e., t shares are needed to reclaim one secret). Therefore, the original Shamir's (t, n) SS is very inefficient as a conveyor of information (Blakley and Meddows, 1984). MSS, which allows multiple secrets to be shared among shareholders, is proposed to improve the efficiency of Shamir's (t, n) SS. There are various proposals of MSS. For example, MSSs proposed by Dehkordi and Mashhadi (2008), Shao and Cao (2005), Zhao et al. (2007) are based on polynomials. The security of these MSSs is based on some cryptographic assumptions and therefore, they are computationally secure.

In this paper, we propose a strong (n, t, n) VSS which is more efficient than Harn and Lin's strong (n, t, n) VSS (Harn and Lin, 2010). Following the same approach, we propose the efficient (n, t, n) MSS and (n, t, n) VMSS. All proposed algorithms are unconditionally secure. We summarize contributions of this paper below.

  • An efficient strong (n, t, n) VSS which enables shareholders to verify their shares is proposed.

  • An efficient (n, t, n) MSS which enables shareholders to share n  t + 1 secrets is proposed.

  • An efficient (n, t, n) VMSS which enables shareholders to verify their shares and to share n  t secrets is proposed.

  • All proposed schemes are unconditionally secure.

In Section 2, we provide some preliminaries, including Shamir's (t, n) SS, the definitions of t-consistency and strong t-consistency, and the strong (n, t, n) VSS proposed by Harn and Lin (2010). In Section 3, we propose an efficient strong (n, t, n) VSS. Section 4 presents an efficient (n, t, n) MSS and the (n, t, n) VMSS. The conclusion is included in Section 5.

Section snippets

Preliminaries

Benaloh (1987) proposed a notion of t-consistency of a (t, n) SS. The property of t-consistency can be used to check the consistency of shares.

Definition 1

t-Consistency of shares (Benaloh, 1987). A set of n shares, s1, s2,…, sn is t-consistent if any subset containing t shares defines the same secret.

Benaloh (1987) observed that shares, s1, s2,…, sn in Shamir's (t, n) SS are t-consistent if and only if the interpolation of values (1, s1), (2, s2),…, (n, sn) yields a polynomial of degree at most t  1.

The proposed strong (n, t, n) VSS

In this paper, we propose an efficient strong (n, t, n) VSS, in which the sub-shares of the master secret are used for verification purpose. Notice that in Harn and Lin's scheme each shareholder needs to generate k additional verification sub-polynomials and sub-shares for the verification.

The homomorphism property of the following summation of polynomialsF(x)=f1(x)+f2(x)++fn(x)has been used in the design of the (n, t, n) SS and strong (n, t, n) VSS (Harn and Lin, 2010). The homomorphism

The proposed (n, t, n) MSS

In this section, we propose a (n, t, n) MSS that allows shareholders to share n  t + 1 secrets by using n  t + 1 linearly independent sets of weight vector (w1,w2,,wn). The proposed (n, t, n) MSS is outlined in Scheme 5.

Theorem 4

The proposed (n, t, n) MSS shares up to n  t + 1 linearly independent master secrets securely.

Proof

First, we want to show that the n  t + 1 multiple master secrets shared in the proposed (n, t, n) MSS are linearly independent. In other words, we want to prove that any master secret in our

Conclusion

We propose a strong (n, t, n) VSS to verify the strong t-consistency of shares. This proposed scheme is more efficient than Harn and Lin's strong (n, t, n) VSS which was published most recently. In Harn and Lin's VSS, shareholders need to utilize 100 verification polynomials to verify the strong t-consistency of master shares. In our VSS, shareholders utilize the sub-polynomials of master secret to construct a verification polynomial and use them to verify master shares. In addition, we propose

Acknowledgments

This work is supported in part by Testbed@TWISC, National Science Council under the Grant NSC 100-2219-E-006-001, the National Science Foundation of China under Grant Nos. 60970140, 60773135, 90718007, the National High-Tech Research and Development Program of China (863 Program) under Grant Nos. 2007AA01Z427, 2007AA01Z450.

Yan-Xiao Liu is currently a Ph.D. student in Xidian University, China. His current research interests include secret sharing and its applications.

References (18)

There are more references available in the full text version of this article.

Cited by (34)

  • Secure cloud-of-clouds storage with space-efficient secret sharing

    2021, Journal of Information Security and Applications
    Citation Excerpt :

    There are a few solutions to this problem in the literature. A first class of solutions are multi-secret sharing schemes, i.e., schemes that improve space efficiency by sharing several secrets together [28–31]. However, this approach is not suitable for cloud storage as files are typically stored one by one in the cloud, not in groups of several files of the same size.

View all citing articles on Scopus

Yan-Xiao Liu is currently a Ph.D. student in Xidian University, China. His current research interests include secret sharing and its applications.

Lein Harn received the B.S. degree in electrical engineering from the National Taiwan University in 1977, the M.S. degree in electrical engineering from the State University of New York-Stony Brook in 1980, and the Ph.D. degree in electrical engineering from the University of Minnesota in 1984. In 1984, he joined the Department of Electrical and Computer Engineering, University of Missouri- Columbia as an assistant professor, and in 1986, he moved to Computer Science and Telecommunication Program (CSTP), University of Missouri, Kansas City (UMKC). While at UMKC, he went on development leave to work in Racal Data Group, Florida for a year. His research interests include cryptography, network security, and wireless communication security. He has published a number of papers on digital signature design and applications and wireless and network security. He has written two books on security. He is currently investigating new ways of using secret sharing in various applications.

Ching-Nung Yang received the B.S. and M.S. degrees, both from the Department of Telecommunication Engineering, National Chiao Tung University, Hsinchu, Taiwan, in 1983 and 1985, respectively, and the Ph.D. degree in electrical engineering from National Cheng Kung University, Tainan, Taiwan, in 1997. From 1987 to 1989, and from 1990 to 1999, he was with the Telecommunication Laboratory and with the Training Institute Kaohsiung Center, Chunghwa Telecom Company, Ltd., Kaohsiung, respectively. He is currently a Full Professor with the Department of Computer Science and Information Engineering, National Dong Hwa University, Hualien, Taiwan, and is also an IEEE senior member. He has published a number of journal and conference papers in the areas of information security and coding theory. He is the coeditor of the book “Visual Cryptography and Secret Image Sharing” published by CRC Press. His current research interests include coding theory and multimedia security.

Yu-Qing Zhang is a professor and supervisor of Ph.D. students of Graduate University of Chinese Academy of Sciences. He received his B.S. and M.S. degrees in computer science from Xidian University, China, in 1987 and 1990, respectively. He received his Ph.D. degree in Cryptography from Xidian University in 2000. His research interests include cryptography, wireless security, and trust management.

View full text