
Citation: Xingxing Jia, Yixuan Song, Daoshun Wang, Daxin Nie, Jinzhao Wu. A collaborative secret sharing scheme based on the Chinese Remainder Theorem[J]. Mathematical Biosciences and Engineering, 2019, 16(3): 1280-1299. doi: 10.3934/mbe.2019062
[1] | Lina Zhang, Jing Zhang, Jiaqi Sun, Qingpeng Chen . A global progressive image secret sharing scheme under multi-group joint management. Mathematical Biosciences and Engineering, 2024, 21(1): 1286-1304. doi: 10.3934/mbe.2024055 |
[2] | Xuehu Yan, Longlong Li, Lintao Liu, Yuliang Lu, Xianhua Song . Ramp secret image sharing. Mathematical Biosciences and Engineering, 2019, 16(5): 4433-4455. doi: 10.3934/mbe.2019221 |
[3] | Xiaoping Li, Yanjun Liu, Hefeng Chen, Chin-Chen Chang . A novel secret sharing scheme using multiple share images. Mathematical Biosciences and Engineering, 2019, 16(6): 6350-6366. doi: 10.3934/mbe.2019317 |
[4] | Feng Liu, Xuehu Yan, Lintao Liu, Yuliang Lu, Longdan Tan . Weighted visual secret sharing with multiple decryptions and lossless recovery. Mathematical Biosciences and Engineering, 2019, 16(5): 5750-5764. doi: 10.3934/mbe.2019287 |
[5] | Li-na Zhang, Chen-yu Cui, Xiao-yu Zhang, Wei Wu . Adaptive visual cryptography scheme design based on QR codes. Mathematical Biosciences and Engineering, 2022, 19(12): 12160-12179. doi: 10.3934/mbe.2022566 |
[6] | Song Wan, Guozheng Yang, Lanlan Qi, Longlong Li , Xuehu Yan, Yuliang Lu . Multiple security anti-counterfeit applications to QR code payment based on visual secret sharing and QR code. Mathematical Biosciences and Engineering, 2019, 16(6): 6367-6385. doi: 10.3934/mbe.2019318 |
[7] | Li-na Zhang, Jia-qi Sun, Xiao-yu Zhang, Qing-peng Chen, Jing Zhang . Two-level QR code scheme based on region matrix image secret sharing algorithm. Mathematical Biosciences and Engineering, 2023, 20(9): 16678-16704. doi: 10.3934/mbe.2023743 |
[8] | Ching-Chun Chang, Chang-Tsun Li . Algebraic secret sharing using privacy homomorphisms for IoT-based healthcare systems. Mathematical Biosciences and Engineering, 2019, 16(5): 3367-3381. doi: 10.3934/mbe.2019168 |
[9] | Yanjun Liu, Chin-Chen Chang, Peng-Cheng Huang . Security protection using two different image shadows with authentication. Mathematical Biosciences and Engineering, 2019, 16(4): 1914-1932. doi: 10.3934/mbe.2019093 |
[10] | Guozheng Yang, Lintao Liu, Xuehu Yan . A compressed secret image sharing method with shadow image verification capability. Mathematical Biosciences and Engineering, 2020, 17(4): 4295-4316. doi: 10.3934/mbe.2020237 |
Online collaboration among multiple entities becomes a very popular application nowadays due to automatic data backup and cross-regional group collaboration requirements in cloud computing. The collaborative and sharing nature of data storage in the cloud demands greater group collaborations [1,2]. However, each participating entity would like to protect its privileges before outsourcing its data to the cloud servers. One feasible solution is to use secret sharing (SS) to enable group key management in the distributed fashion, so that the distrusting entities with conflicting interest can cooperate honestly and securely. In a (k,n)-SS scheme, the secret is shared among a number of participants. Due to the flexibility and convenience of cloud computing, the participants often need to participant in different SS sharing systems in different applications. If we just use the traditional SS scheme to design the management system, a participant joining in multiple management systems, called multi-privilege participant, will need to store multiple shares in each application, which is inconvenient. Consider the following scenario concerning data sharing.
With the development of big data and artificial intelligence (AI), data with multiple owners are often needed to be agammaegated to accomplish an important task by using AI techniques. For example, the financial datas from cities A, B and C are running in a cooperated and distributed manner to analyze an economic development index as illustrated in Figure 1. The financial data, traffic data, population data of city A is used to analyze the urban construction planning. The financial data from city A is used in different group collaborative tasks. A convenient and secure data management system is the first consideration for such confidential data against untrusted cloud. This phenomenon has become more common in cloud data collaboration among different data owners. The data owner of city A must carry two shares to manage the data in different collaborative tasks. If a data owner is involved in a large number of data collaborative tasks, he or she needs to keep many shares, which can be a burden.
Therefore, it is desirable to have a SS scheme such that each multi-privilege participant needs to keep only one share in its related tasks. Not only it will be more convenient for the participants, but also the multiple key management systems can be made more practical. In this paper, we just propose such a scheme based on the Chinese Remainder Theorem (CRT).
The SS schemes were first introduced by Shamir [3] and Blakley [4] independently to share a secret among a group of n participants. It allows the secret to be reconstructed when more than the threshold k of these participants are working together, but less participants cannot recover the secret. Thanks to its high level of security protection and low computatonal requirements, SS schemes have been used in various applications, such as human-verifiable authentication [5], group collaboration [6,7], and secure multiparty computation [8]. Nowadays, with the popularity of cloud computing, SS schemes have emerged as an important technology for secure data storage in the cloud, secure group management [9,10,11], and reputation adjustment in social network [12,13].
In a (k,n) SS scheme, the regular participant can obtain only one share. The multi-privilege participant who has more privileges will receive multiple shares, which is inconvenient. In cloud computing environments, group collaboration between two or more management systems is widely used in the era of shared economy [14]. Consider the following scenario regarding group collaboration: a participant joins in multiple reputation systems in the social network and she will have multiple reputation values using secret sharing schemes [13,12,15]. A collaborative reputation management system will allow this multi-privilege participant to share her reputation in different platforms. In general, the above scenarios can be described as a cryptographic model: a multiple secret sharing scheme is designed to share multiple secrets independently, while the participants and the secrets have the many-to-many relationships. Inspired by the practical problems arisen in the above scenarios, it is desirable to design a scheme to facilitate the group collaboration among different threshold secret sharing schemes so that each multi-privilege participant only needs to keep one share.
How to collaborate between threshold secret sharing schemes was first proposed by [16] to solve bank managers with multiple privileges problem. In their scheme, if u participants are involved in both schemes, each of these u multi-privilege participant keeps only one share by constructing polynomials with common solutions. Here we call the participants who are involved in multiple SS schemes as multi-privilege participants, and their shares are called multi-privilege shares. Each secret can be uniquely reconstructed by Lagrange interpolation, but it requires O(klog2k) operations. The collaborative visual cryptographic scheme was formulated as an integer linear programming problem that minimizes pixel expansion under the corresponding security and contrast constraints in [11]. Each multi-privilege participant takes one share and can reconstruct the secret together with the other participants when they belong to the designated qualified subsets family. The secret can be visually recovered without any computation but with lower quality. The scheme has strict constraints for the participant intersection [16]. The collaborative visual scheme will suffer from severe pixel expansion problem. Hence, it will become impractical when the participant intersections are complex [11]. Since a group collaboration in the cloud may involve flexible and complex computations, participant intersections are also complex. Therefore, it is desirable to construct a collaborative secret sharing (CSS) scheme to allow complex participant intersections and to recover the secret perfectly with lower computational complexity.
Another important mathematical model to address the threshold SS scheme is the Chinese Remainder Theorem (CRT), which requires only O(k) operations in the secret reconstruction phase [17,18]. The scheme in [18] is proved by [20,24,21,19] having asymptotically perfect security and is practical due to its high efficiency and simple construction. The CRT has been extensively used in various SS schemes and has produced abundant research results. Shares in the (k,n) SS scheme based on the CRT form a redundant representation of the secret, which provides a number-theoretic construction of an "error-correcting code" in [21]. The threshold changeable secret sharing scheme in [22] is a lattice-based "error-correction" algorithm that can be seen as an application of the algorithm in 'Noisy Chinese Remaindering in the Lee Norm' [23]. It is accomplished based on CRT by adding noise to the shares. Intensive analysis of the security was presented in [24], and the prime sequence generation algorithm for the Asmuth-Bloom scheme was proposed for the first time. A multi-level threshold scheme [25] was constructed by using the CRT. Harn et al. devised the general secret sharing scheme [26] based on the CRT with Boolean logic and integer linear/non-integer programming. Drǎgan and Ţiplea proposed the distributive weighted threshold SS scheme [27], which has perfect zero-knowledge. In order to decrease the recovery complexity, we consider to use the CRT to construct the collaborative secret sharing scheme in this paper.
Inspired by the previous works in [16] and [18], we present a novel scheme to solve the collaboration problem based on CRT, which can reconstruct the secret with the same security as in scheme [18]. The computational complexity is only O(k) in the secret reconstruction phase. Our method avoids high complexity, and restrictive participant intersections of [16], and the low recovery quality and extremely large pixel expansion of [11]. The compromise is that our scheme needs to publish n moduli as the public parameters comparable with one parameter in [16,11]. The advantage of its single share and lower computation complexity make our approach ideal for high-through processing applications. It will provide an efficient outsourced computation platform which will facilitate the group collaboration among different secret-data owners. The proposed scheme can be used as a building block to handle different types of group collaborations.
In summary, the contributions of this paper are summarized as follows. A collaborative secret sharing scheme framework is proposed, in which the Chinese Remainder Theorem is used to lower the computational complexity. It can fully achieve the group collaboration functionality and security requirements. This contributes to a better performance than comparative state-of-the-art polynomial methods. Complex participant intersections are designed so that each multi-privilege participant just keeps one share even if multiple secrets are shared. Our approach to building CSS scheme may have some independent interests, and it may find applications in related cryptographic protocols.
The remainder of this paper is organized as follows. Section 2 gives the definition of SS scheme using entropy terms, the preliminaries of the CRT, the SS scheme based on the CRT [18]. Section 3 gives the definition of collaboration between two schemes and presents the algorithm design. Collaboration among three or more schemes is different from the collaboration between two schemes in terms of participant intersection and the presentation format, which is addressed in the same section. The correctness and security are analysed in Section 4, followed by the comparison of performance between the proposed scheme and the schemes in [16] and [11]. One example is presented to demonstrate the construction process. Finally, conclusions are drawn in Section 5.
In this section, we review the key building blocks, including the definition of SS scheme, the Chinese Remainder Theorem and Asmuth-Bloom's scheme used in our scheme.
SS scheme is an important key management technique by decomposing a secret into input shares. The (k,n) secret sharing scheme is the common used SS schemes, where n is the number of participants and k(≤n) is called threshold, which is pre-determined according to the security policy or the adversary model. The scheme has perfect security if participants not belonging to the access structure obtain no information about the secret. The access structure refers to the qualified subset holding at least k shares which can recover the secret.
Let P={P1,⋯,Pn} be a set of n participants, S⊆{0,1}x be a finite set of secrets, called the secret-domain, and R be a set of random strings. H(⋅) stands for the Shannon entropy and H(⋅|⋅) denotes the conditional entropy. A secret sharing scheme over P is a mapping Π:S×R→S1×⋯×Sn, where Si is called the share-domain of Pi. Dealer shares a secret s∈S among the participants according to Π by first sampling a random string r∈R, computing the shares (S1,⋯,Sn), and then privately communicating each share Si to Pi. For any subset A∈P, SA denotes the set of shares held by all participants in A. There are multiple forms of definitions for (k,n) SS scheme. From the information theory point of view, its definition is widely used to demonstrate its performance. In present study, we adopt the definition from [28].
Definition 2.1. (Secret Sharing Scheme [28]). A (k,n) threshold secret sharing scheme over a participant set P is a secret sharing scheme Π:S×R→S1×⋯×Sn satisfying the following two conditions:
1. for all A⊆P and |A|≥k, H(S|SA)=0;
2. for all A⊆P and |A|<k, 0<H(S|SA)≤H(S).
A scheme is called perfect if H(S|SA)=H(S) holds for all A⊆P and |A|<k. A scheme is called asymptotically perfect if for all ϵ>0, there exists x0≥0 such that for all A⊆P with x≥x0, we have that
△H=|H(S)−H(S|SA)|≤ϵ |
holds for all |A|<k (see the definition 4 in section 2 [20]).
Theorem 1. (Chinese Remainder Theorem [30]). If p1,p2,…,pk are pairewise coprime positive integers, then the following equations of congruence
{S≡S1modp1,S≡S2modp2,⋯,S≡Skmodpk, | (2.1) |
have a unique solution
S≡k∑i=1PpiSiyimodP, | (2.2) |
where P=k∏i=1pi, Ppiyi≡1modpi, and "≡" denotes the relation of congruence.
The CRT states that a positive integer S is uniquely specified by its remainder modulo k relatively prime integers p1, p2, ⋯, pk, provided S<k∏i=1pi. The CRT has been used in RSA decryption to accelerate the decryption process [30]. It is also well known in communication applications as error-correction codes [30] and image encryption [31]. The CRT can also be used to design various SS schemes [18,17,22,27,26,25,29]. The SS scheme based on CRT uses a special sequence of integers to guarantee the security and recovery of the secret. In our scheme, we use the CRT to design a CSS scheme, which can be seen as an extended application of CRT. In the next subsections, we will review the well-known SS scheme [18] based on the CRT.
The SS schemes based on the CRT were designed by Mignotte [17] and Asmuth, Bloom [18], respectively. The SS scheme uses a special increasing sequence of pairwise coprime integers satisfying formula (2.3) to achieve asymptotically perfect security [18] and is widely used as the fundamental scheme to construct related SS schemes [22,25,26,27]. The Asmuth-Bloom SS scheme is given in the following.
Distribution phase
1. Select relatively prime integers p0<p1<⋯<pn, where p0 is a large secure prime, and the n+1 primes satisfy the following relationship
k∏i=1pi>p0k−1∏i=1pn−i+1. | (2.3) |
2. The dealer selects a secret s∈Zp0 and computes S=s+α⋅p0, where α is a random positive integer satisfying the condition k−1∏i=1pn−i+1<S<k∏i=1pi (This formula is enhanced in security by Harn and Fu in [25] from 0<S<k∏i=1pi in [18]).
3. The share for participant i is Si≡Smodpi, i∈{1,2,…,n}.
Reconstruction phase
1. Let A be the participant set that reconstructs the sharing secret with k or more participants. The participants send their shares to the combiner secretly.
2. The combiner computes
S≡∑i∈ASiP′A∖{i}PA∖{i}modPA |
and obtains secret s by s≡Smodp0. Set PA=∏i∈Api and PA∖{i}=∏j∈A,j≠ipj. P′A∖{i} is the multiplicative inverse of PA∖{i} in Zpi, which means that we have P′A∖{i}PA∖{i}≡1modpi.
This section first presents the collaboration between two SS schemes in which each multi-privilege participant holds only one share. Then, the collaboration among more SS schemes is constructed. We assume each scheme is constructed by the trusted third party. We call it the dealer. Different dealers are honest to transfer the necessary information and will not collude with any participants. In this paper, we emphasize on the basic model construction.
Assume two secrets s1 and s2 are concealed in a (k1,n1) scheme among participants in the set P1={P11,…,P1n1} and a (k2,n2) scheme among participant set P2={P21,…,P2n2} separately, where k1,n1,k2,n2∈Z+. The multi-privilege participant set is denoted as U=P2⋂P1={P2,11,…,P2,1u} with |U|=u, the three values u, k1 and k2 are not equal. The collaborative scheme between two SS schemes is denoted as a ((k1,n1);(k2,n2))-CSS scheme with U. In order to protect each shared secret against colluding attacks, we generally require u<min{k1,k2}. It means that the recovery of each secret requires at least one internal participant who doesn't participant in any other SS scheme. A formal definition of the ((k1,n1);(k2,n2))-CSS scheme with U is given below.
Definition 2 A (k1,n1)-SS scheme with participant set P1={P11,…,P1n1} to share a secret s1 and a (k2,n2)-SS scheme with participant set P2={P21,…,P2n2} to share a secret s2 constitute a ((k1,n1);(k2,n2))-CSS scheme with U, where U=P2⋂P1={P2,11,…,P2,1u} and |U|=u if the following two conditions are satisfied:
1. for all A⊆P1 and |A|≥k1, H(s1|SA)=0; for all A⊆P2 and |A|≥k2, H(s2|SA)=0;
2. for all A⊆P1⋃P2 and |A⋂P1|<k1, 0<H(s1|SA)≤H(s1); for all A⊆P1⋃P2 and |A⋂P2|<k2, 0<H(s2|SA)≤H(s2).
The first condition ensures that each secret can be revealed correctly by its authorized subsets. The second condition prevents unauthorized subsets from collusively revealing the secret. When the equality holds in the second condition, the ((k1,n1);(k2,n2))-CSS scheme with U has perfect security. It is called asymptotically perfect if for all ϵ>0, there exists x0≥0 such that for all A⊆P1⋃P2 with x≥x0, we have that
△H=|H(si)−H(si|SA)|≤ϵ |
holds for all |A⋂Pi|<ki, i∈{1,2}.
Since a ((k1,n1); (k2,n2))-CSS scheme with U is a collaborative scheme, we assume that the (k1,n1) scheme is constructed first and then the multi-privilege shares are passed on to the dealer of the (k2,n2) scheme. Each (ki,ni) is an independent Asmuth-Bloom scheme, in addition to satisfying the collaborative conditions. The proposed ((k1,n1); (k2,n2))-CSS scheme with U is presented in Scheme 1.
Scheme 1 The proposed ((k1,n1);(k2,n2))-CSS scheme with U
Distribution phase
1. Dealer 1 chooses a large prime number p0 and a sequence of pairwise coprime positive integers
p0<p1<p2<⋯<pn1 |
such that k1∏i=1pi>p0k1−1∏i=1pn−i+1, where gcd(pi,pj)=1, i≠j for i,j∈{1,2,…,n1}.
2. The dealer selects a secret s1 and a random integer α1, and computes the secret related value S1=s1+α1p0 such that k1−1∏i=1pn−i+1<S1<k1∏i=1pi.
3. Shares for the participants in P1 are generated by
Si,1≡S1modpi |
for i∈{1,2,…,n1} and are sent to them secretly. Dealer 1 chooses the u multi-privilege shares from the n1 shares, assuming s1,1, s2,1, …, su,1 are chosen, and passes them to Dealer 2.
4. Dealer 2 selects a secure large prime number q0 and a sequence of pairwise coprime positive integers
q0<q1<q2<⋯<qn2 |
such that k2∏i=1qi>q0k2−1∏i=1qn−i+1 and Si,1<qi for i∈{1,2,…,u}, where gcd(qi,qj)=1, i≠j for i,j∈{1,2,…,n2}. Such process will maintain the validity of the multi-privilege shares.
5. Dealer 2 chooses the secret s2∈Zq0. Here, we assume that the u multi-privilege shares are also the first u shares of the (k2,n2) SS scheme. The dealer selects a suitable random integer α2 and computes the secret related value S2=s2+α2q0 such that k2−1∏i=1qn−i+1<S2<k2∏i=1qi. By combining the conditions of the multi-privilege shares, we can determine α2 by:
{s2≡S2modq0,S1,2(=S1,1)≡S2modq1,⋯,Su,2(=Su,1)≡S2modqu. | (3.1) |
The secret related value S2 is derived by using (2.2) and then α2 can be derived, which is specified in Remark 1.
6. The shares for the participants in P2 are generated as
Si,2≡S2modqi |
for i=u+1,2,…,n2, and are delivered secretly to them.
Reconstruction phase
1. Given any k1 shares of P1, such as Si1,1, …, Sik1,1, we can find the secret related value S1 according to the CRT by using (2.2) and compute the secret s1≡S1modp0.
2. Similarly, given any k2 shares of P2, for example Si1,2, …, Sik2,2, the secret related value S2 can be computed according to the CRT by using (2.2), and the secret is obtained by s2≡S2modq0.
Remark 1. Step 5 of Scheme 1 is important for the CSS construction. It allows each multi-privilege participant to take only one share to participant multiple SS schemes. Here we show how to determine the secret related value S2. A unique integer w∈(u−1∏i=0qn−i+1,u∏i=0qi] can be determined from (3.1) according to the CRT by using (2.2). We rewrite it in the form w=s2+yq0∈(u−1∏i=0qn−i+1,u∏i=0qi] and calculate the unique integer y. Then we randomly choose x such that S2=w+xq0q1…qu∈(k2−1∏i=1qn−i+1,k2∏i=1qi], this leads to α2=y+xq1…qu since S2=s2+α2q0. Because y is uniquely determined and x has multiple random candidates by the above conditions, α2 has the same random choices as x.
In reality, Scheme 1 cannot be used when u=k1=k2. In reality, u=k1=k2 is not desirable from a security point of view since the u multi-privilege participants are not pure internal participants that they may collude to recover the secret without the authorization of the pure internal participants. It is safer if no more than u participants working together with at least one internal participant should be required to reconstruct the secret, i.e., u<k1 and u<k2.
This subsection discusses cases where three or more threshold schemes collaborate with each other. Each dealer is in charge of one secret and distributes shares to related participants. The participant sets may overlap because the possibility of participants involving in multiple group collaboration is high. Under such circumstance, there may be common participants in any two schemes. The common participants means the multi-privilege participants. We now give an example for the collaboration among three SS schemes.
Example 1. Consider three schemes, a (3,5) scheme to share s1, a (4,6) scheme to protect s2 and a (5,7) scheme for s3. Their participants are denoted as A={A1, A2, A3, A4, A5}, B={B1, B2, B3, B4, B5, B6} and C = {C1, C2, C3, C4, C5, C6, C7}, respectively. The common participants may appear in different subsets of intersection of A and B and C. The basic intersections are shown in Figure 1 and depicted as four cases.
Case 1: The common participants occur in A⋂B⋂C. A1 and A2 are the common participants involved in all three schemes, i.e., A1=B1=C1, A2=B2=C2. It is secure from the point of view of si, i=1,2,3, since none of the other schemes or dealers can reveal the secret of si, i=1,2,3. A diagram is given in Figure 2.(a).
Case 2: The common participants occur in A⋂B. When A1 and A2 are in A⋂B, it is secure in terms of s1 and s2 (Figure 2.(b)).
Case 3: The common participants occur in B⋂C. When B1 and B2 are in B⋂C, it is secure in terms of s2 and s3 (Figure 2.(c)).
Case 4: The common participants occur in C⋂A. When A1 and A2 are in C⋂A, it is secure in terms of s1 and s3 (Figure 2.(d)).
In fact, the common participants may occur in any combination of the above four cases. In different intersection cases, we need to consider different share intersections. This inspires us to propose a new method to define the participant set that the intersections can be seen clearly. For collaboration among l SS schemes, we define the participant set for each (ki,ni) scheme as Pi={pi1,…,pini}, and its access structure is Γi={U⊆Pi,|U|≥ki} for i∈{1,2,…,l}. The shares are generated in order without repetition. We define the intersection in the following manner.
For the first scheme, (k1,n1)-SS scheme, the participants in P1 are defined as
P1={P11,…,P1n1}. | (3.2) |
Then, we define the second participant set P2. If it has common participants with the first participant set, their intersection is defined as U2,1=P1⋂P2={P2,11,…,P2,1u2,1} with |U2,1|=u2,1. Then, the second participants set is expressed as
P2={P2,11,…,P2,1u2,1,P2u2,1+1,…,P2n2}. | (3.3) |
For the third participant set P3, if they have common participants with the first and the second participant sets, we denote them as U3,1=P3⋂P1={P3,11,…,P3,1u3,1} with |U3,1|=u3,1, and U3,2=(P3⋂P2)∖U3,1={P3,21,…,P3,2u3,2} with |U3,2|=u3,2, meeting the requirement that U3,1⋂U3,2=∅. Then, the third participant set can be defined as
P3={P3,11,…,P3,1u3,1,P3,2u3,1+1,…,P3,2u3,1+u3,2,P3u3,1+u3,2+1,…,P3n3}. | (3.4) |
The i-th participant set Pi is assumed to have Ui,1=Pi⋂P1={Pi,11,…,Pi,1ui,1} with |Ui,1|=ui,1, Ui,2=(Pi⋂P2)∖Ui,1={Pi,21,…,Pi,2ui,2} with |Ui,2|=ui,2 and Ui,j=(Pi⋂Pj)∖(j−1⋃s=1Ui,s)={Pi,j1,…,Pi,jui,j} with |Ui,j|=ui,j for j∈{3,…,i−1}, meeting the requirement that Ui,j⋂Ui,k=∅ for j≠k and j,k∈{3,…,i−1}. Therefore,
Pi={Pi,11,…,Pi,1ui,1,Pi,2ui,1+1,…,Pi,2ui,1+ui,2,…,Pi,i−1ui,1+ui,2+⋯+ui,i−2+1,…,Pi,i−1ui,1+ui,2+⋯+ui,i−1,Piui,1+ui,2+⋯+ui,i−1+1,…,Pin3}. |
The remaining n−3 participant sets are defined in the same manner as participant set Pi. Let U=l⋃i=1i−1⋃j=1Ui,j. To maintain the security of each secret, the number of multi-privilege participants for each (ki,ni) SS scheme in Pi should be less than ki. Therefore,
|(l⋃j=1,j≠iPj)⋂Pi|<ki | (3.5) |
holds, so the leakage of secret information through the collusion of the multi-privilege participants can be precluded.
With the above notations, we now give a formal definition of the ((k1,n1);…;(kl,nl))-CSS scheme with U.
Definition 3 A l tuples of the (ki,ni) SS scheme with participant set Pi sharing a secret si, i=1,2,…,l with intersection U constitute a ((k1,n1);…;(kl,nl))-CSS scheme with U depicted as above if the following two conditions hold:
1. for all A⊆Pi and |A|≥ki, H(si|A)=0 for i=1,…,l;
2. for all A⊆l⋃i=1Pi and |A⋂(l⋃j=1Pi)|<ki, 0<H(si|SA)≤H(si) for i=1,…,l.
The first condition ensures that each secret can be revealed correctly by its authorized subsets. The second condition prevents the unauthorized subsets from collusively revealing the secret. When the "=" relation holds in the second condition, the ((k1,n1);…;(kl,nl))-CSS scheme has a perfect security. It is called asymptotically perfect if for all ϵ>0, there exists x0≥0 such that for all A⊆l⋃i=1Pi with x≥x0, we have that △H=|H(si)−H(si|SA)|≤ϵ holds for all |A⋂(l⋃j=1Pi)|<ki where i=1,…,l. We now present the construction scheme of a ((k1,n1); …;(kl,nl))-CSS with U.
Scheme 2 The proposed ((k1,n1);…;(kl,nl))-CSS with U
Distribution phase
1. Dealer 1 chooses a large prime number p0,1 and a sequences of pairwise coprime positive integers,
p0,1<p1,1<p2,1<⋯<pn1,1, |
satisfying k1∏i=1pi,1>p0,1k1−1∏i=1pn1−i+1,1, gcd(pj,1,pk,1)=1, j≠k for j,k∈{1,2,…,n1}. Dealer 1 selects a secret s1∈Zp0,1 and a random integer α1, and computes the secret related value S1=s1+α1p0,1 such that S1∈(ϕ1k1−1,ϕ1k1]. Here, we set ki∏j=1pj,i=ϕiki and ki−1∏j=1pni−j+1,i=ϕiki−1 for 1≤i≤l. Shares for the participants in P1 are generated as
Sj,1≡s1+α1p0,1modpj,1, |
where j∈{1,2,…,n1}. Dealer 1 picks the ui,1 multi-privilege shares {Si,11,…,Si,1ui,1} and passes them to Dealer i.
2. Dealer 2 receives the u2,1 multi-privilege shares {S2,11,…,S2,1u2,1} from U2,1. Then, he/she chooses a large prime number p0,2 and a sequence of pairwise coprime positive integers,
p0,2<p1,2<p2,2<⋯<pn2,2, |
satisfying k2∏i=1pi,2>p0,2k2−1∏i=1pn2−i+1 and S2,1j<pj,2 for 1≤j≤u2,1, where gcd(pj,2,pk,2)=1, j≠k for j,k∈{1,2,…,n2}.
Dealer 2 selects a secret s2∈Zp0,2 and a random integer α2 and computes the secret related value S2=s2+α2p0,2 satisfying the condition S2∈(ϕ2k2−1,ϕ2k2] and the following congruent equations:
{s2≡S2modp0,2,S1,2(=S2,11)≡S2modp1,2,⋯,Su2,1,2(=S2,1u2,1)≡S2modpu2,1,2. | (3.6) |
Here, we assume that the multi-privilege participants in U2,1 are the first u2,1 participants in P2. The integer α2 can be determined according to Remark 1. The remaining n2−u2,1 shares Sj,2 can be determined by using
Si,2=S2modpi,2. |
Dealer 2 distributes shares S1,2, S2,2, …, Sn2,2 to participants in P2 privately. Dealer 2 also sends multi-privilege shares {Si,21, Si,22, …, Si,2ui,2} to Dealer i for i∈{3,…,l}.
3. Dealer i receives shares {Si,j1, Si,j2, …, Si,jui,j} from dealer j, j∈{1,…,i−1}, i∈{3,4,…,l}. Then, he/she chooses a large prime number p0,i and a sequence of pairwise coprime positive integers,
p0,i<p1,i<p2,i<⋯<pni,i, |
satisfying ki∏j=1pj,i>p0,iki−1∏j=1pni−j+1 and with Si,jk<pk,i for 1≤k≤ui,j, where gcd(pj,i,pk,i)=1, j≠k for j,k∈{1,2,…,ni}. Dealer i selects a secret si∈Zp0,i and a random integer αi, and computes the secret related value Si=si+αip0,i satisfying Si∈(ϕiki−1,ϕiki] and the following congruent equations:
{si=Simodp0,i,Si,1(=Si,11)≡Simodp1,i,⋯,Si,ui,1(=Si,1ui,1)≡Simodpui,1,i,}→Ui,1,Si,ui,1+1(=Si,21)≡Simodpui,1+1,i,⋯,Si,ui,1+ui,2(=Si,2ui,2)≡Simodpui,1+ui,2,i,}→Ui,2,Sui,1+ui,2+⋯+ui,j−1+1,i(=Sj,i1)≡Simodpui,1+ui,2+⋯+ui,j−1+1,i,⋯,Sui,1+ui,2+⋯+ui,j,i(=Si,jui,j)≡Simodpui,1+ui,2+⋯+ui,j,i,}→Ui,j, 3≤j≤i−1. | (3.7) |
Here, we assume that the common participants in Ui,j appear in Pi in increasing order of i,j. The integer αi can be determined according to Remark 2 below. Then, Dealer i computes the shares for the remaining participants in set Pi by
Sj,i≡Simodpj,i, |
for ui+1≤j≤ni. Let ui=ui,1+ui,2+⋯+ui,i−1. Dealer i sends shares Sj,i to participants in Pi and the multi-privilege shares {Sj,i1, Sj,i2, …, Sj,iuj,i} to Dealer j for j=i+1,…,l.
Reconstruction phase
Given any ki shares of Pi, such as Sj1,i, …, Sjki,i, we can find the secret related value Si according to the CRT by using (2.2) and compute the secret si≡Simodp0,i, i∈{1,2,…,l}.
Remark 2. Step 3 in Scheme 2 is the key point to construct the CSS scheme. It allows each multi-privilege participant to take one share to manage multiple secrets. The secret can be randomly chosen by each dealer. Here we show how to determine the secret related value Si. The unique integer wi can be evaluated from (3.7) according to the CRT by using (2.2). Then, we can determine αi=yi+xip1,i…pu,i according to
Si=wi+xip0,ip1,i…pui,i∈(ki−1∏j=1pn−j+1,i,ki∏j=1pj,i],wi=si+yip0,i∈(ui−1∏j=0pn−j+1,i,ui∏j=0pj,i]. |
Because yi and wi are uniquely determined from (3.7), and x has multiple random candidates under the above condition, the variable αi has the same random choices as the variable xi.
In this section, we analyse the performance of the proposed scheme in terms of security and correctness. The performance comparison with previous collaborative schemes is shown. The experiments demonstrate the construction process of CSS proposed scheme and verify the two characteristics.
It is clear that the security of the proposed scheme is the same as that of the scheme in [18] because each single scheme in the CSS scheme satisfies the security condition (2.3). The shares of multi-privilege participants who are involved in multiple secrets have more tendency to be attacked. The regular participants have the same role and security as that they have in a single SS scheme. Therefore, we consider three possible attacks with respect to multi-privilege participants and illustrate them in the following.
● The multi-privilege participants cannot recover any secret independently because of (3.5).
● The multi-privilege participants' unity with the participants in Γi cannot recover the corresponding secret si if their number is less than its threshold ki.
● The multi-privilege participants' unity with the participants in Pi cannot recover the secret sj(j≠i) if their number is less than the related threshold. Furthermore, even if their number is not less than the related threshold, no knowledge about sj will be leaked, because |(U⋃Pi)⋂Pj)|≤kj−1.
It is easy to verify that the three styles of attack will not succeed in obtaining any useful knowledge because they all satisfy condition (3.5). The multi-privilege participants are unlikely to obtain secret information. The proposed CSS scheme is secure against k−1 colluding participants.
The key point of the construction of CSS scheme is that each secret is still chosen randomly by its dealer and is not affected by the generated multi-privilege shares. Conditions (3.1) and (3.7) can guarantee that the secret s can be chosen randomly and the secret related value S can be calculated to satisfy the security requirement of CSS. The reasons are illustrated in the Remark 1 and Remark 2. When the threshold of any single scheme is reached, the secret can be evaluated by solving congruent equations using the CRT. The correctness of the proposed scheme is clear. The correctness and security proofs are presented in Theorem 2.
Theorem 2. The proposed CSS scheme based on the CRT is a asymptotically perfect ((k1,n1);…;(kl,nl))-CSS scheme with U.
Proof. We need to prove its correctness and asymptotically perfect security.
Before we prove the asymptotically perfect security, the proposed scheme needs to be validated. We show that for all A⊆Pi and |A|≥ki, where i∈{1,2,…,l}, the secret can be recovered correctly from the shares in A. Assuming that A={i1,i2,⋯,i|A|}, we collect their shares Si1,i,Si2,i,⋯,Si|A|,i and have the following equations of congruence:
{Si≡Si1,imodpi1,i,Si≡Si2,imodpi2,i,⋯,Si≡Si|A|,imodpi|A|,i. | (4.1) |
The moduli of the above congruent equations satisfy ∏j∈A,|A|≥tipj,i≥ϕiki. Because we know the secret related value Si∈(ϕiki−1,ϕiki], it can be uniquely determined from the above equations of congruence by using the CRT. Then, we compute si=Simodp0 to obtain the secret si.
We prove its the asymptotically perfect security in the following. We show the security for the proposed scheme. The first two types of attack satisfy the condition of (3.5) and belong to the unauthorized subset of Si. No useful information will be leaked. The third type attack fulfills the condition |(U⋃Pi)⋂Pj|<kj and belongs to the unauthorized subset of Sj. Now we prove that the entropy loss of the secret derived from the the unauthorized share subset of Sj is negligible for j∈{1,2,…,l}.
Firstly, we derive the candidates of the secret related value by the shares of the unauthorized subset of Sj. Let A⊆Pj be the unauthorized subset of Sj. Its shares Sir,j, ir∈A with |A|<tj, for the threshold tj are collected and constitute the following congruent equations:
{Sj≡Si1,jmodpi1,j,Sj≡Si2,jmodpi2,j,⋯,Sj≡Si|A|,jmodpi|A|,j. | (4.2) |
There is a unique solution X∈(0,∏i∈Api,j) for (4.2) according to Theorem 1. The candidates of the secret related value are Sj=X+y⋅∏i∈Api,j according to the CRT, where y∈{1,…,C(A)} with C(A)≜⌊∏1≤i≤tjpi,j/∏i∈Api,j⌋. Since Sj∈(ϕjkj−1,ϕjkj] and p0,jϕjkj−1<ϕjkj, we can derive that
C(A)>p0,j−1, | (4.3) |
from ∏i∈Api,j≤ϕjkj−1.
Secondly, we compute the conditional entropy of the secret by the known shares SA from the unauthorized subset of Sj. The secret candidates can be derived by s=Sj(modp0,j). The number of secret candidates is not reduced according to (4.3). Let C(A)=p0,jN+r with 0≤r<p0,j. The C(A) candidates of secret related value Sj are mapped to p0,j secret candidates. The secret candidates which will appear N+1 times and N times are denoted by s1={sj1,sj2,…,sjr} and s0={sr+1,sr+2,…,sp0,j}, respectively. The two sets satisfy both s0⋂s1=∅ and s0⋂s1=Zp0,j. Given shares SA, we compute the conditional entropy of the secret,
H(s|SA)=−r∑i=1pilogpi−p0,j∑i=r+1pilogpi=−rN+1C(A)logN+1C(A)−(p0,j−r)NC(A)logNC(A). |
H(s|SA) can be lower bounded as
H(s|SA)>rN+1C(A)logC(A)N+1+(p0,j−r)NC(A)logC(A)N+1=logN+1C(A), |
and upper bounded as
H(s|SA)<−rN+1C(A)logNC(A)−(p0,j−r)NC(A)logNC(A)=logC(A)N. |
We obtain that logC(A)N+1<H(s|SA)<logC(A)N.
Thirdly, we compute the loss of entropy of the secret △H. The entropy of the secret satisfies H(s)=logp0,j since s∈RZp0,j.
△H=|H(s)−H(s|SA)|=|log(1±rC(A))|<logp0,jC(A). | (4.4) |
By hypothesis, the prime pi,js are consecutive for 1≤i≤nj. It follows that pi+1,j<pi+p12+121i for pi sufficiently large (See [32], p. 193). Because the primes pi,j's are consecutive, it holds that, for all sufficiently large p0,j
C(A)+1≥pt0,j/(pt−10,j+∑iaipbi0), |
where ai∈R+ and 0<bi<t−1, for all i. For all sufficiently large prime p0,j, it holds
p0,jC(A)≤p0,j(pt−10,j+∑iaipbi0)/(pt0,j−pt−10,j−∑iaipbi0). |
Applying the logarithm operator and using (4.4), we get
△H=|H(s)−H(s|SA)|≤logp0,j(pt−10,j+∑iaipbi0)/(pt0,j−pt−10,j−∑iaipbi0). |
The upper bound converges to 0 when p0,j converges to infinity. Thus, the asymptotically perfect security is proved.
The efficiency of the proposed scheme is compared with that of the previous CSS scheme in terms of share size, broadcast message size, security, recovery complexity and recovery quality in Table 1. From Table 1, we can see that scheme [16] requires high recovery complexity with the exact reconstructed secret. The scheme in [11] has zero computational complexity in the recovery phase, but it decreases the visual effect of the secret and expands the share size. The proposed CSS scheme can reconstruct the secret exactly with lower recovery complexity. Furthermore, it can process complex participant intersections. It provides broad applications for group collaborations.
Scheme | Share size | Security | Computation complexity | Recovery quality |
CSS([16]) | H(S) | perfect | O(klog2k) | exact |
CVS([11]) | mH(S) | perfect | 0(visual) | lower |
ours | H(S) | perfect | O(k) | exact |
Remark. m(>1) is the pixel expansion which is determined by the detailed scheme. |
The proposed CSS scheme is different from the multi-secret sharing scheme [34,33]. But it can be used to construct such schemes when u=0 or ui,j=0. Under such application, it has the same structure with the multi-secret sharing scheme which allows a single secret to be shared per threshold value [34,33]. But such multi-secret sharing schemes cannot be used to construct the proposed CSS scheme. The CSS scheme has special collaborative properties that general multi-secret sharing schemes don't have.
To demonstrate the construction strategy of the collaborative schemes, two numerical examples are used to illustrate our proposed scheme. A ((3,5);(4,6))-CSS with its U is shown in Example 2 by combining step 1 and step 2. A ((3,5);(4,6);(5,7))-CSS with its U is obtained by combining step 1, step 2 and step 3. The experimental results also demonstrate the correctness and security of the proposed CSS scheme.
Example 2. Suppose there are three secrets (s1, s2 and s3) that can be protected by three dealers with three traditional threshold schemes as a (3,5) scheme, a (4,6) scheme and a (5,7) scheme, respectively. The participant intersections are shown in Figure 3. Five participants with the first secret form the group P1={A1,A2,A3,A4,A5}, and six participants with the second secret form the group P2={B1(A1),B2(A2),B3,B4,B5,B6}, and seven participants with the third secret form the group P3={C1(A2),C2(B3),C3,C4,C5,C6,C7}. The share generation process is conducted in three steps as follows. The main parameters are shown in Table 2. The multi-privilege shares are labelled with the asterisks.
Scheme | i | p0,i | si | (pi,1,Si,1) | (pi,2,Si,2) | (pi,3,Si,2) | (pi,4,Si,4) | (pi,5,Si,5) | (pi,6,Si,6) | (pi,7,Si,7) |
(3, 5) | 1 | 113 | 112 | (119, 80∗) | (211, 16∗∗) | (223, 51) | (227, 66) | (229,115) | −− | −− |
(4, 6) | 2 | 151 | 150 | (263, 80∗) | (269, 16∗∗) | (271, 260∗∗∗) | (277,249) | (281, 46) | (283, 72) | −− |
(5, 7) | 3 | 191 | 178 | (397, 16∗∗) | (401, 260∗∗∗) | (409,155) | (419,215) | (421,120) | (431,363) | (433,313) |
Remark. 80∗ denotes the multi-privilege share for for A1(B1); 16∗∗ denotes the multi-privilege for A2(B2, C1); 260∗∗∗ denotes the multi-privilege for B3(C2). |
Step 1: Share construction for a (3,5) scheme.
The secret s1=112 and p0,1=113, and the pairwise coprime numbers and shares are shown in Table 2. Because Z(Φ1k1−1,Φ1k1]=Z(51983,9363547], we have α1∈[461,82863] such that S1=s1+α1p0,1∈Z(Φ1k1−1,Φ1k1]. We take α1=1000, S1=113112. Shares for the participants in P1 can be computed by Sj,1≡113112modpj,1. The multi-privilege participant sets are U2,1={p1,1,p2,1}, U3,1={p2,1}. Share 80 for participant A1(B1) and share 16 for participant A2(B2,C1) are picked and handed over to Dealer 2. Share 16 for participant A2(C1) is handed over to Dealer 3.
Step 2: Share construction for the (4,6) scheme.
Dealer 2 chooses a secret s2=150, p0,2=151, and a sequences of pairwise coprime positive integers shown in Table 2. Dealer 2 already has two shares: 80 and 16 and the secret 150. By using (3.1) and Remark 2, the unique solution w2=9317907∈(39713,10682797] is obtained. We can take a random variable x2 such that S2=w+x2p0,2p1,2p2,2∈Z(Φ2k2−1,Φ2k2]=Z(22027871,5310765049]. Assuming x2=300, then S2=9317907+300⋅10682797=3214157007∈Z(Φ2k2−1,Φ2k2]. Thus, α2=21285807. The remaining shares can be generated as sj,2=S2modpj,2 for 3≤j≤6. The generated shares are shown in Table 2.
Step 3: Share construction for the (5,7) scheme.
Dealer 3 already receives shares S3,11=16 for C1 and S3,21=260 for C2. He or she chooses randomly s3=178, p0,3=191 and the sequences of pairwise coprime positive integers to constructs a (5, 7) threshold scheme shown in Table 2. The shares (191,178), (397, 16), and (401,260) are used to generate the secret related value S3. By using formula (3.7) and Remark 2, the unique solution w3=7298861∈(75827,30406627] is obtained. Since S3=w3+x32∏j=0pj,3∈Z(Φ3k3−1,Φ3k3]=Z(32920110577,11485616365627], it is derived that x3∈Z(1082,377733]. We choose x3=99999 and obtain S3=7298861+99999⋅30406627=3040639592234∈Z(Φ3k3−1,Φ3k3]. The remaining shares can be generated using Sj,3=S3modpj,3 for 3≤j≤7.
The ((3, 5); (4, 6))-CSS scheme with its U can be verified correct. When any three participants of the first (3, 5) scheme present their shares, for example, (211, 16), (223, 51), and (227, 66), then the first secret is obtained as
S1≡16×50621×111+51×47897×144+66×47053×188mod211223227=113112,s1≡113112mod113=112. |
The correctness and security for the ((3, 5);(4, 6);(5, 7))-CSS with its U can be verified in the same manner. It is clear that the collaborative scheme can reveal each secret correctly when the participant sets are in the corresponding qualified subsets family. The participant set which includes all multi-privilege participants belongs to the unqualified subsets family of any secret and cannot obtain any information about that secret. The multi-privilege shares uniting the participants in Pi cannot obtain any secret information about sj when i≠j. The conclusions can be verified by using the data in Example 2. The CSS scheme has the same asymptotically perfect security as that of the Asmuth-Bloom scheme.
In this paper, we proposed a collaborative SS scheme which provides a secure and efficient strategy to ease the share management in group collaborative environment. Each participant just needs to keep only one share to participate in multiple key management systems. It can solve the contradiction between privacy protection and collaborative sharing of confidential data. It can be used for secure data management across systems or joint computing platforms. Its efficiency and convenience in operation are attractive in distributed networks. The comparative study of the proposed scheme with the state of the art approaches validates its efficiency.
The collaborative scheme raises a number of related open problems, such as security concerns involving dishonest multi-privilege participants, dishonest dealers in different schemes, and the situation where other dealers become participants of a scheme. Various combinations of risks exist in this "open" environment. For example, some dishonest multi-privilege participants could work with other illegal participants or dealers to steal secrets. Tracing traitors could become more difficult than in the traditional single scheme situation.
This work was supported the National Natural Science Foundation Nos. U1636219, 61872289, and 41807150, in part by Plan for Scientific Innovation Talent of Henan Province No. 2018JR0018 and the Science Foundation of Guangxi Nos. AA17204096 and AD16380076, in part by China Mobile Research Fund Project No. MCM20170407, and Key Laboratory of Digital Content Anti-Counterfeiting and Security Forensics of the state Administration of Press, Publication, Radio, Film and Television of the People's Republic of China.
All authors declare no conflicts of interest in this paper.
[1] | Y. Liu, Y. Wang, X. Wang, Z. Xia and J. Xu, Privacy-preserving raw data collection without a trusted authority for IoT, Comput. Netw., 1 (2018), 1–1. |
[2] | Y. Liu, W. Guo, C. Fan, L. Chang and C. Cheng, A practical privacy-preserving data aggregation (3PDA) Scheme for Smart Grid, IEEE T. Ind. Inform., 1 (2018), 1–1. |
[3] | A. Shamir, How to share a secret, Commun. ACM, 22 (1979), 612–613. |
[4] | G. R. Blakley, Safeguarding cryptographic keys, in Proceedings of the 1979 AFIPS National Computer Conference, AFIPS Press, (1979), 313–317. |
[5] | C. N. Yang, L. Z. Sun, X. Yan, and C. Kim, Design a new visual cryptography for human-verifiable authentication in accessing a database, J. Real-Time Image Process., 12 (2016), 483–494. |
[6] | L. Harn, Group authentication, IEEE Trans. Comput., 62 (2013), 1893–1898. |
[7] | L. Harn and C. Lin, Authenticated group key transfer protocol based on secret sharing, IEEE Trans. Comput., 59 (2010), 842–846. |
[8] | S. Wüller, D. Mayer, F. Förg, S. Schüppen, B. Assadsolimani, U. Meyer and S. Wetzel, Designing privacy-preserving interval operations based on homomorphic encryption and secret sharing techniques, J. Comput. Secur., 25 (2017), 1–23. |
[9] | D. Agrawal, A. E. Abbadi, F. Emekci, A. Metwally and S.Wang, Secure data management service on cloud computing infrastructures, Springer Berlin Heidelberg, (2011), 57–80. |
[10] | Y. Wang, Privacy-preserving data storage in cloud using array BP-XOR codes, IEEE T. Cloud Comput., 3 (2015), 425–435. |
[11] | X. Jia, D. Wang, D. Nie and C. Zhang, Collaborative visual cryptographic schemes, IEEE Trans. Circuits Syst. Video Technol., 28 (2018), 1056–1070. |
[12] | M. Nojoumian, D. R. Stinson and M. Grainger, Unconditionally secure social secret sharing scheme, IET Inf. Secur., 4 (2010), 202–211. |
[13] | S. Song and K. Hwang and R. Zhou and Y. K. Kwok, Trusted P2P transactions with fuzzy reputation aggregation, IEEE Internet Comput., 9 (2005), 24–34. |
[14] | J. S. Lin, Cloud data storage with group collaboration supports, in International Conference on Networked Digital Technologies, Springer Berlin Heidelberg, (2011), 423–431. |
[15] | F. M´armol and G. M. Pérez, TRIP, A trust and reputation infrastructure-based proposal for vehicular ad hoc networks, J. Netw. Comput. Appl., 35 (2012), 934–941. |
[16] | D. Wang, Z. Ye and X. Li, How to collaborate between threshold schemes, preprint, (2013), arXiv:1305.1146. |
[17] | M. Mignotte, How to share a secret, in Proceedings of the Workshop on Cryptography Burg Feuerstein, Springer Berlin Heidelberg, (1983), 371–375. |
[18] | C. Asmuth and J. Bloom, A modular approach to key safeguarding, IEEE Trans. Inf. Theory, 29 (1983), 208–210. |
[19] | C. C. Drăgan and F. L. Tiplea, On the asymptotic idealness of the Asmuth-Bloom threshold secret sharing scheme, Inf. Sci., 463-464 (2018), 75–85. |
[20] | B. Preneel and J. Vandewalle, On the security of the threshold scheme based on the Chinese Remainder Theorem, in International Workshop on Public Key Cryptography 2002, Springer- Verlag, (2002), 199–210. |
[21] | O. Goldreich, D. Ron and M. Sudan, Chinese remaindering with errors, IEEE Trans. Inf. Theory, 46 (2000), 1330–1338. |
[22] | R. Steinfeld, J. Pieprzyk and H. Wang, Lattice-based threshold-changeability for standard CRT secret-sharing schemes, Finite Fields their Appl., 12 (2006), 653–680. |
[23] | I. E. Shparlinski and R. Steinfeld, Noisy Chinese Remaindering in the Lee norm, J. Complex., 20 (2004), 423–437. |
[24] | Y. H. Liu and R. J. Chen, An asymptotically perfect secret sharing scheme based on the Chinese Remainder Theorem, Int. J. Comput. Math., 94 (2017), 1890–1915. |
[25] | L. Harn and F. Miao, Multilevel threshold secret sharing based on the Chinese Remainder Theorem, Inf. Process Lett., 114 (2014), 504–509. |
[26] | L. Harn, C. Hsu, M. Zhang, T. He and M. Zhang, Realizing secret sharing with general access structure, Inf. Sci., 367 (2016), 209–220. |
[27] | C. C. Drăgan and L. F. T¸ iplea, Distributive weighted threshold secret sharing schemes, Inf. Sci., 339 (2016), 85–97. |
[28] | K. M. Martin, J. Pieprzyk, S. N. Rei and H. Wang, Changing thresholds in the absence of secure channels, in Proceedings of the 4th Australasian Conference on Information Security and Privacy, Springer Berlin Heidelberg, (1999), 177–191. |
[29] | X. Jia, D.Wang, D. Nie, X. Luo and J. Z. Sun, A new threshold changeable secret sharing scheme based on the Chinese Remainder Theorem, Inf. Sci., 473 (2019), 13–30. |
[30] | C. Ding, D. Pei and A. Salomaa, Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography, World Scientific Press, 1996. |
[31] | C. Li, Y. Liu, L. Y. Zhang and K.-W. Wong, On the asymptotic idealness of the Asmuth-Bloom threshold secret sharing scheme, Signal Process Image, 29 (2014), 914–920. |
[32] | P. Ribenboim, The Book of Prime Number Records, 2nd edition, Springer-Verlag, New York, 1994. |
[33] | J. Shao and Z. Cao, A new efficient (t ,n)verifiable multi-secret sharing (VMSS) based on YCH scheme, Appl. Math. Comput., 168 (2005), 135–140. |
[34] | C. W. Chan and C. C. Chang, A scheme for threshold multi-secret sharing, Appl. Math. Comput., 166 (2009), 1–14. |
1. | Zhen Wu, Yining Liu, Xingxing Jia, A Novel Hierarchical Secret Image Sharing Scheme with Multi-Group Joint Management, 2020, 8, 2227-7390, 448, 10.3390/math8030448 | |
2. | Xiaogang Wang, Zhongfan Yang, Zhiqiang Feng, Jun Zhao, A WSN Layer-Cluster Key Management Scheme Based on Quadratic Polynomial and Lagrange Interpolation Polynomial, 2020, 20, 1424-8220, 4388, 10.3390/s20164388 | |
3. | Yi Jiang, Yong Shen, Qingyi Zhu, A Lightweight Key Agreement Protocol Based on Chinese Remainder Theorem and ECDH for Smart Homes, 2020, 20, 1424-8220, 1357, 10.3390/s20051357 | |
4. | Xingxing Jia, Yusheng Guo, Xiangyang Luo, Daoshun Wang, Chaoyang Zhang, A perfect secret sharing scheme for general access structures, 2022, 595, 00200255, 54, 10.1016/j.ins.2022.02.016 | |
5. | Liu Jinwang, Wu Tao, Li Dongmei, Chinese remainder theorem of modules over multivariate polynomial rings, 2022, 52, 1674-7216, 989, 10.1360/SSM-2021-0017 | |
6. | Nikolay N. Shenets, On modular (CRT-based) secret sharing, 2024, 20, 2263-8733, 765, 10.1007/s11416-024-00530-4 | |
7. | Yinong Song, Zichen Li, 2024, Multi-secret Threshold Sharing Scheme Based on Chinese Remainder Theorem, 979-8-3503-5169-9, 131, 10.1109/ICICSE61805.2024.10625673 |
Scheme | Share size | Security | Computation complexity | Recovery quality |
CSS([16]) | H(S) | perfect | O(klog2k) | exact |
CVS([11]) | mH(S) | perfect | 0(visual) | lower |
ours | H(S) | perfect | O(k) | exact |
Remark. m(>1) is the pixel expansion which is determined by the detailed scheme. |
Scheme | i | p0,i | si | (pi,1,Si,1) | (pi,2,Si,2) | (pi,3,Si,2) | (pi,4,Si,4) | (pi,5,Si,5) | (pi,6,Si,6) | (pi,7,Si,7) |
(3, 5) | 1 | 113 | 112 | (119, 80∗) | (211, 16∗∗) | (223, 51) | (227, 66) | (229,115) | −− | −− |
(4, 6) | 2 | 151 | 150 | (263, 80∗) | (269, 16∗∗) | (271, 260∗∗∗) | (277,249) | (281, 46) | (283, 72) | −− |
(5, 7) | 3 | 191 | 178 | (397, 16∗∗) | (401, 260∗∗∗) | (409,155) | (419,215) | (421,120) | (431,363) | (433,313) |
Remark. 80∗ denotes the multi-privilege share for for A1(B1); 16∗∗ denotes the multi-privilege for A2(B2, C1); 260∗∗∗ denotes the multi-privilege for B3(C2). |
Scheme | Share size | Security | Computation complexity | Recovery quality |
CSS([16]) | H(S) | perfect | O(klog2k) | exact |
CVS([11]) | mH(S) | perfect | 0(visual) | lower |
ours | H(S) | perfect | O(k) | exact |
Remark. m(>1) is the pixel expansion which is determined by the detailed scheme. |
Scheme | i | p0,i | si | (pi,1,Si,1) | (pi,2,Si,2) | (pi,3,Si,2) | (pi,4,Si,4) | (pi,5,Si,5) | (pi,6,Si,6) | (pi,7,Si,7) |
(3, 5) | 1 | 113 | 112 | (119, 80∗) | (211, 16∗∗) | (223, 51) | (227, 66) | (229,115) | −− | −− |
(4, 6) | 2 | 151 | 150 | (263, 80∗) | (269, 16∗∗) | (271, 260∗∗∗) | (277,249) | (281, 46) | (283, 72) | −− |
(5, 7) | 3 | 191 | 178 | (397, 16∗∗) | (401, 260∗∗∗) | (409,155) | (419,215) | (421,120) | (431,363) | (433,313) |
Remark. 80∗ denotes the multi-privilege share for for A1(B1); 16∗∗ denotes the multi-privilege for A2(B2, C1); 260∗∗∗ denotes the multi-privilege for B3(C2). |