Verifiable Secret Sharing Scheme Based on the Plane Parametric Curve ()
1. Introduction
In the field of information security, as an important means of key management, the basic principle of secret sharing is to split the master key into many subkeys, and then distribute these subkeys to all members of the set
composed of a limited number of participants. After some members of the authorization set show their subkeys, they can reconstruct the original master key through a series of calculations. But other members of the unauthorized set cannot recover the master key. Therefore, in essence, secret sharing is an operation process for the distribution, preservation and recovery of secret keys. Using the secure sharing scheme in the secret system can not only reduce the burden of the key holder due to the loss and damage of the system key, but also reduce the success rate of the adversary’s malicious attack on the key.
The earliest secret sharing is
-threshold secret sharing, which was proposed by Shamir [1] and Blakley [2] respectively in 1979. Their
-threshold secret sharing schemes are based on the
-threshold access structure on the authorization set composed of at least r members. The difference is the
-threshold scheme of Shamir is realized by constructing a polynomial function over a finite field, and distributing each numerical point coordinate on the function curve as a subkey to the members of each authorization set, and taking the constant term of the polynomial as the master key; The
-threshold scheme of Blakley is realized by constructing n common hyperplanes in multidimensional space, the coordinates of each hyperplane are regarded as a subkey and distributed to the members of each authorization set, and the coordinates of the common intersection of these hyperplanes are regarded as the master key. The results show that the Shamir scheme with the algebraic method is a complete and ideal scheme, while the Blakley scheme with geometric method is a complete and nonideal scheme. Therefore, the information rate of the Blakley scheme is lower than that of the Shamir scheme, but it has the advantage that any subkey vector that can determine the master key point is linearly independent of each other, so it is difficult to guess. In addition to the number method proposed by Shamir and the shape method proposed by Blakley, the methods of constructing
-threshold secret sharing scheme are followed by the method of Asmuth-Bloom [3] based on Chinese remainder theorem, the method of Karnin-Green-Hellman [4] based on matrix multiplication, and the design ideas of the above-mentioned threshold schemes are improved according to different application requirements, and a variety of variants of threshold schemes are proposed [5] [6] [7] [8].
The efficiency of a secret sharing scheme depends on its information rate. It is often said that the information rate of the secret sharing scheme is the ratio of the information amount of the master key to the information amount of the subkeys owned by the participating members. When the amount of information of the master key is a fixed value, from the standpoint of the dealer in charge of the master key, the less the amount of information given to the participating members, the better the security of the secret sharing scheme can be maintained. From the perspective of participants, it is easier to keep the subkey with less information than that with more information. Therefore, a good secret sharing scheme can reduce the amount of subkey information as much as possible. It can be seen that a high information rate is the pursuit of cryptographers. The higher the information rate of the secret sharing scheme, the smaller the degree of data diffusion is. Therefore, people hope to build a secret sharing scheme with the highest information rate. When the information rate reaches the value 1, the corresponding secret sharing scheme will become an ideal secret sharing scheme.
As a technical means, the secret sharing scheme based on a certain mathematical thinking method mentioned above can only solve the most basic problems in key management, but in the actual application environment, it cannot judge whether there is cheating behavior, and it is difficult to prevent some members of the secret sharing scheme from cheating by using a fake subkey to participate in the construction of the master key. Whether it is the cheating of a single member or the collusion of multiple members, it will cause other honest members to get the wrong master key, which will bring great threat and damage to the secret sharing scheme. Therefore, in order to solve the problem of cheating, people need to study how to set up the anti-cheating function of the secret sharing scheme.
As early as 1981, McEliece and Sarwate [9] designed a threshold secret sharing scheme to prevent cheating by using error-correcting code theory. This scheme enables
members with at most e cheaters to correctly construct the master key. If some parameter conditions are given, then the cheating prevention secret sharing scheme can detect the cheating behavior with high probability [10] [11] [12] [13]. If the cheater has supercomputing power, but the probability of success is not more than a small fixed percentage, so we can say that the secret sharing scheme is unconditionally secure in preventing deception [14]. At present, for the existing secret sharing schemes which can detect deception, when a member reconstructs and recovers the master key, it is generally necessary to use some mathematical verification formula to test the subkeys provided by all members one by one. In this way, we can find out which members are cheaters, but when all members are honest, the cost of the verification process is not reduced, which leads to unnecessary waste of resources. This paper proposes a verifiable secret sharing scheme based on the plane parameter curve. It only needs to put the subkeys provided by each member together and check once to determine whether there are cheaters in these members. If it exists, it will terminate the reconstruction immediately, otherwise, it will continue, which greatly improves the efficiency of the secret sharing scheme.
2. Design of the Secret Sharing Scheme
Let Fp be a finite field of p elements and p be a large prime number, let:
,
.
The parametric curve
on affine plane A2(Fp) is introduced:
where f(t) and g(t) are polynomials on Fp.
The parametric curve
satisfies the following additional conditions:
1) For any
, there is
.
2) For any
, let:
If
, then
.
Let D be the distributor of the subkeys, that is, the dealer, and
be the set of n participating members.
Firstly, the dealer D secretly chooses the master key
, decomposes k into r different numbers
on
, that is,
,
, and then constructs the homogeneous formula:
The dealer D secretly selects n different parameters on Fp to calculate
so that any r numbers of
are mutually prime, that is,
.
The dealer D distributes
to the corresponding i-th member
as his subkey.
If r participating members
are going to reconstruct the master key k, they show their subkeys
respectively, and establish the following linear equations on Fp,
(1)
where
.
The system of equations is a linear system of equations consisting of r equations with r variables
and the coefficient matrix H is a generalized Vander monde matrix on Fp, obviously, under the additional condition of parameter curve
, the matrix
. Since
, the system of equations has a unique solution on Fp, that is:
where:
Then the r participating members calculate:
to recover the master key.
For this
-threshold scheme, a problem can be raised: whether there are members who provide false subbeys in the stage of r participating members reconstructing the master key, that is, how each member can judge whether someone in other members has cheated and provided untrue subkeys, which requires the dealer to give parameter or parameter groups for verification, Let’s first introduce the following two lemmas.
Lemma 1. Let r ≥ 2, N and
be positive integers, and
. There is a positive integer
only related to
when
the equation:
(2)
has a set of nonnegative integer solutions
.
Proof. Mathematical induction is used for r.
When r = 2 we choose
, because:
, (3)
where
, all solutions of Equation (3) can be expressed as:
where
are a group of special solutions of Equation (3), and u is any integer.
Obviously, u can be taken so that
, i.e.
when
, the following is true:
,
that is:
.
Therefore, for the above u, there is:
.
So when
there is an integer solution
in (3).
Let’s suppose that the lemma holds for r − 1 elements. It is proved that the lemma holds for r elements.
Let
,
, and
be obtained from
, therefore there exists
such that
.
Let
, and from (2) we can get:
(4)
Since
, by inductive assumption, there is an integer
, when
, the indefinite Equation (4) has a set of nonnegative integer solutions:
That is, when
, the indefinite Equation (2) has a set of nonnegative integer solutions
.
This completes the proof.
If we take
, where m is a sufficiently large positive integer such that
then the indefinite equation:
(5)
has a set of nonnegative integer solution
.
Dealer D selects a primitive root g of module p calculates:
and then exposes array
as the verification parameter group of participants.
Lemma 2. If a is the primitive root of module n, then
if and only if
, where
is an Euler function, and
when n is a prime p.
Proof. From the condition, we get
, so there is
where
is the exponent of a to module n, thus we get:
.
Since a is the primitive root of module n, that is
, thus:
.
The above proof process is reverible, which completes the proof of Lemma 2.
According to these two lemmas, we can get the following judgment theorem.
Theorem 1. For the subkey group
provided by the participating member in P, if
, then there must be cheaters in the participating member set.
Proof.
can be obtained, and:
can be obtained from Lemma 2.
If there is no cheater in the members, then:
,
thus:
.
According to the equivalent logical relationship between the original proposition and its converse proposition, we get that if the subkey group
provided by the participating members satisfies
, then
, it means that there must be cheaters in the participating members. This completes the proof of Theorem 1.
For example, let
, when
, there is
, so that
.
At this time, there is:
,
,
and:
.
If
in the participant submits a false subkey
, then:
.
3. Performance Analysis of the Secret Sharing Scheme
Theorem 2. The
-threshold scheme is a complete and ideal secret sharing scheme.
Proof. If any r members
take out their respective subkeys together, then we can build linear Equations (1). Obviously, there are r variables in this system of equations.
According to the corresponding relationship of each subkey, it is necessary for r members to join together to construct a linear system of equations containing r equations, so as to obtain the unique solution containing the master key and this solution also satisfies the equation generated by the subkeys held by other members. Therefore, at least members must be together to recover the shared master key k and less than r members cannot find the unique solution of the linear equations, so no information of the master key k can be obtained. In conclusion, the
-threshold scheme is a complete secret sharing scheme.
Let S = Fp, master key
, since each participant has only one subkey of secret value, and all values are in S, we can calculate the information rate [15]:
So the
-threshold scheme is also an ideal secret sharing scheme. It’s over.
Theorem 3. For this
-threshold secret sharing scheme, the probability of success of h (1 ≤ h < r) cheaters in the participating members is
.
Proof. Suppose r members
are about to reconstruct and recover the master key k in which there are h (1 ≤ h < r) cheaters.
Let
be cheaters and
be honest people. If
use false data
to impersonate the real subkeys
respectively, and
show their correct subkeys, then the equations to obtain the reconstructed master key k from the public information become:
(6)
Because the system of Equations (6) contains
,
total of h + r unknown variables and r + 1 equations, so there are h − 1 free variables, so the system of Equations (6) has
different solutions. Since all the possible subkey sets of cheaters
contain
elements, the probability of successful deception of
is:
It’s over.
It can be seen from Theorem 3 that for the threshold secret sharing scheme, when h = 1 the probability of success of deception is 0, that is, a single cheater will not succeed in deception; With the increasing number of success is also increasing; However, no matter how many cheaters there are, the probability of success of cheaters will not exceed 1/p.
4. Conclusion
At present, among some verifiable secret sharing schemes that have been published, the secret sharing schemes described in references [10] [11] are complete, but not ideal. Although the secret sharing scheme designed in references [12] [13] is perfect and ideal, it needs to test the subkeys of each participant one by one, resulting in the inefficiency of the scheme itself. In this paper, the plane parameter curve is used to construct the threshold secret sharing scheme, which can make the curve coordinates and the homogeneous formula of determining the master key expressed by the same parameter t, thus showing the advantages of the single parameter representation of the master key, reducing the amount of information contained in the subkeys, increasing the information rate, and making the secret sharing scheme more practical and easy to implement. The results show that the threshold scheme is not only complete, but also ideal; at the same time, it has verifiability. Through the one-time operation, we can judge whether there are cheaters in the participating members, and the probability of successful deception of the cheater will not exceed 1/p. Therefore, the secret sharing scheme is effective and unconditionally secure in preventing deception. Secret sharing has very important theoretical and practical significance in key management. We plan to study the next research topic. We will study the construction of a higher standard secret sharing scheme based on the parametric elliptic curve equation [16] [17] to further strengthen the security and effectiveness of secret sharing.