A new efficient (t, n) verifiable multi-secret sharing (VMSS) based on YCH scheme
Introduction
In order to keep the secret efficiently and safely, Shamir [7] and Blakley [1] presented (t, n) threshold secret sharing scheme, respectively, in 1979. In such a scheme, the dealer splits the secret into shares among servers, and sends the share to the corresponding server. As a result, any t out of the n servers can cooperate to resume the secret, but any less than t out of the n servers can’t get any useful information about the secret by any way. A threshold secret sharing scheme has many practical applications, such as opening a bank vault, launching a nuclear, or authenticating an electronic funds transfer. Later, several multi-secret sharing schemes were proposed. In a multi-secret sharing scheme, there are multiple secrets to be shared during one secret sharing process, such as [4], [8].
In most of above schemes, it is supposed that the dealer and the servers are honest, but in fact, it is impossible in the real world. In literature [2], Chor and Goldwasser presented the verifiable secret sharing (VSS) to solve this problem, and Feldman [5] proposed a non-interactive verifiable secret sharing scheme in 1987. Furthermore, Harn [6] presented the verifiable multi-secret sharing (VMSS) in 1995. But in his scheme, in order to verify whether the secret shadow is valid, every server must check n!/((n − t)!t!) equations, and the progress is interactive. In addition, the shared secrets must be fixed in advance. So it is difficult to realize. Later, Chen et al. [3] presented another VMSS to improved some drawbacks in [6], but the cost of computing in it is still high. In this paper, we present a new efficient VMSS based on the YCH [8] scheme and the intractability of the discrete logarithm (DL).
This rest of this paper is organized as follows. In Section 2, we briefly review YCH [8] scheme. In Sections 3 Our VMSS, 4 Performance analysis, we present our new (t, n) VMSS based on YCH [8] and make some discussions. Finally, we present our conclusions in Section 5.
Section snippets
Review of YCH [8] scheme
In this section, we briefly review YCH [8]. Function f(r, s) denotes any two-variable one-way function that maps a secret shadow s and a value r onto a bit string f(r, s) of a fixed length. The properties of the function, we suggest that the readers refer to [8]. Here, (P1, P2, … , Pk) denotes k secrets to be shared among n servers.
Before the secret sharing, the dealer randomly chooses n secret shadows s1, s2, … , sn and distributes them to every server by a secret channel. Then the dealer performs the
Our VMSS
Our VMSS notations (f(r, si), (P1, P2, … , Pk)) are the same as those of YCH [8] scheme, and p is a safe prime, such as q∣(p − 1), where q is a big prime, and g is the generator of order q over GF(p). The dealer first randomly chooses n secret shadows s1, s2, … , sn and distributes them to every server by a secret channel. Then the dealer randomly chooses an integer r and computes f(r, si) for i = 1, 2, … , n. Then the dealer performs the following steps:
- •
ifk ⩽ t
- –
Choose a prime q and construct (t − 1)th degree
- –
Performance analysis
Our scheme has the following advantages:
- •
every server verify his secret shadow only by one equation,
- •
our scheme also resist the servers’ cheating behavior only by one equation and the progress is non-interactive,
- •
we add the verifiable property into YCH [8], and our VMSS still has the properties of YCH [8] scheme,
- •
our VMSS needs to only publish (n + 1 + t) or (2k + n + 1 − t) values.
Conclusion
In this paper, we presents a new efficient VMSS based on YCH [8] scheme and the intractability of the discrete logarithm (DL). It not only has the non-interactive verifiable property, but also still has the properties of YCH [8]. Furthermore, our VMSS needs few public values and low modular exponentiation operation. Of course, we discuss how to check the dealer’s and servers’ cheating behave in the case of secret channel. If there is no secret channel, we can use signature into our scheme to
Acknowledgement
This research is partially supported by the National Natural Science Foundation of China for Distinguished Young Scholars under Grant No. 60225007 and the National Research Fund for the Doctoral program of Higher Education of China under Grant No. 20020248024.
References (8)
- et al.
A (t, n) multi-secret sharing scheme
Appl. Math. Comput.
(2004) - G.R. Blakley, Safeguarding cryptographic keys, in: Proc. AFIPS 1979 NCC, vol. 48, Arlington, VA, June 1979, pp....
- et al.
Verifiable secret sharing and achieving simultaneity in the presence of faults [A]
- et al.
Secret sharing with reusable polynomials [A]