CN108111485B - Sub-key generation method and device and key reduction method and device - Google Patents

Abstract

The present invention provides a method for generating a sub-key, a method for restoring a key, a device for generating a sub-key and a device for restoring a key under a multi-threshold access structure, wherein the method for generating a sub-key includes: determining a secret key according to the key s Step of key correlation value S, using {pi _,j } to calculate

steps, and will

The i-th row element in {s _i,1 ,s _i,2 ,...,s _i,m } is the step assigned to the i-th participant's subkey. This method can realize the access structure of any integer threshold between (t,n) and (t',n), and the generated subkey can carry more (t'-t)/ (t-1) times share (t'-t+1) thresholds. Compared with (t'-t+1) independent threshold schemes, the sub-key length increase in this invention is only 1/(t-1) of the original. And there is complete security under each threshold scheme.

Description

Subkey generation method and device, and method and device for restoring key

technical field

The present invention relates to key management in the field of security information, in particular to a method for generating a subkey, a distribution device, and a method and device for restoring a key by using the subkey.

Background technique

Key management is an important protocol in distributed cryptography and distributed computing. It can establish a fair and trustful cooperative relationship among a group of conflicting interests but must cooperate, making the distributed security system robust.

Because the (t,n)(t≤n) threshold scheme has the advantages of strong security, full homomorphism, low complexity and simple operation, it has been widely used in key management (privacy protection, authentication systems, etc.) in recent years. trust computing, trust management, secure multi-party computation).

The (t,n) threshold scheme distributes an important key in the group of participants, so that each participant carries only one sub-key, uses no less than t sub-keys, and puts them together for reconstruction The algorithm can reconstruct the key, but the key cannot be reconstructed with no more than t-1 subkeys. Among them, t is generally determined by the security access strategy, adversary attack capability and user convenience.

In the prior art, the threshold scheme only considers one security requirement when constructing, and does not consider the decrease of system security caused by the change of the attack power of the adversary with the passage of time. In order to overcome the security solution problem caused by the long-term use of a single threshold scheme, the distribution and use of subkeys that allow the threshold to change dynamically has become a solution considered in the art.

SUMMARY OF THE INVENTION

The present invention provides a method for generating a subkey, a method for restoring a key by using the subkey, and a device corresponding to the foregoing method, which are used for realizing the distribution of the subkey with the dynamic threshold change and restoring the key by using the subkey.

The present invention provides a method for generating a subkey, comprising the following steps:

素数p₀∈(2^λ-1,2^λ]；S101, determine the key correlation value S according to the key s, wherein

prime number p ₀ ∈(2 ^λ-1 ,2 ^λ ];

中的元素s_i,j≡S mod p_i,j，其中p_i,j是素数矩阵

中的元素，i∈{1,2,...,n}，j∈{1,2,...,m}；S102, calculation

elements in s _i,j ≡S mod p _i,j , where p _i,j is a matrix of prime numbers

elements in , i∈{1,2,...,n}, j∈{1,2,...,m};

满足关系式：

和

前述关系式中，

l∈{1,…,m}，n为参与者总数，t为最小参门限，t'为最大门限，2≤t≤t'≤n，m为可调整的门限总数，t+m-1＝t'；the prime number matrix

Satisfy the relation:

and

In the above relationship,

l∈{1,...,m}, n is the total number of participants, t is the minimum parameter threshold, t' is the maximum threshold, 2≤t≤t'≤n, m is the total number of adjustable thresholds, t+m-1 = t';

中的第i行元素{s_i,1,s_i,2,...,s_i,m}为分配给第i个参与者的子密钥。S103: Extraction

The i-th row elements in {s _i,1 ,s _i,2 ,...,s _i,m } are the subkeys assigned to the i-th participant.

Optionally, the key-related value S is determined according to the key s according to the following steps:

以使S∈(a_m,b_m]。S=s+αp ₀ ; the selection range of random number α is

so that _{S∈(am ,b m ]} .

中的元素按照下述方法获得：Optionally, the prime number matrix

The elements in are obtained as follows:

Select n prime numbers from the interval (2 ^λ-1+t'-1 ,2 ^λ-1+t' ] and assign them to {p _1,m ,p _2,m ,...,p _n,m } element;

中随机选取n个素数赋值给{p_1,l,p_2,l,...,p_n,l}中的元素，其中l∈{1,2,…,m-1}。According to the value of l in descending order, from the interval

Randomly select n prime numbers from and assign them to the elements in {p _1,l ,p _2,l ,...,p _n,l }, where l∈{1,2,...,m-1}.

Optionally, the method further includes:

S104: The sub-key {s _i,1 ,s _i,2 ,...,s _i,m } is encrypted and distributed to the i-th participant by using public key encryption or private key encryption.

On the other hand, the present invention also provides a method for restoring a key, which is characterized in that, comprising:

i_r∈A，|A|≥t_l，

其中，l∈{1,2,…,m}，t+m-1＝t'，t≤t'≤n，n为参与者总数，t为最小门限，t'为最大门限，m为可调整的门限总数；S501: In the case where the _lth threshold tl is activated (tl=t+ _l - ₁ ), obtain the subkeys of at least tl participants

i _r ∈A, |A|≥t _l ,

Among them, l∈{1,2,...,m}, t+m-1=t', t≤t'≤n, n is the total number of participants, t is the minimum threshold, t' is the maximum threshold, m is the available threshold The total number of thresholds adjusted;

的子矩阵

计算密钥相关值S，其中

S502: Utilize the prime number matrix

submatrix of

Calculate the key correlation value S, where

S503: Restore the key s according to the key-related value S.

Optionally, restore the key s according to the key-related value S according to the following steps:

s=S mod p ₀ , where p ₀ is a prime number p ₀ in .

On the other hand, the present invention provides a sub-key generation device, comprising:

素数p₀∈(2^λ-1,2^λ]；The key correlation value calculation unit is used to determine the key correlation value S according to the key s, wherein

prime number p ₀ ∈(2 ^λ-1 ,2 ^λ ];

中元素s_i,j＝S mod p_i,j，其中p_i,j是素数矩阵

中的元素，i∈{1,2,…,n}，j∈{1,2,…,m}；Subkey calculation unit, used to calculate

element s _i,j =S mod p _i,j , where p _i,j is a matrix of prime numbers

elements in , i∈{1,2,…,n}, j∈{1,2,…,m};

满足关系式：

和

前述关系式中，

l∈{1,…,m}，t为最小门限，t'为最大门限，t≤t'≤n，m为可调整的门限总数，t+m-1＝t'；the prime number matrix

Satisfy the relation:

and

In the above relationship,

l∈{1,...,m}, t is the minimum threshold, t' is the maximum threshold, t≤t'≤n, m is the total number of adjustable thresholds, t+m-1=t';

中的元素{s_i,1,s_i,2,...,s_i,m}为分配给第i个参与者的子密钥。Subkey determination unit, used to convert

The elements in {s _i,1 ,s _i,2 ,...,s _i,m } are the subkeys assigned to the i-th participant.

Optionally, the key-related value calculation unit determines the key-related value S according to the key s according to the following steps:

以使S∈(a_m,b_m]。S=s+αp ₀ ; the selection range of random number α is

so that _{S∈(am ,b m ]} .

中的元素按照下述方法获得：Optionally, the prime number matrix

The elements in are obtained as follows:

Randomly select n prime numbers from the interval (2 ^λ-1+t'-1 ,2 ^λ-1+t' ] and assign them in order as {p _1,m ,p _2,m ,...,p _n,m };

中随机选取n个素数按照顺序赋值为{p_1,l,p_2,l,...,p_n,l}，其中l∈{1,2,…,m-1}。According to the value range of l {1,...,m-1} from large to small in order from the interval

Randomly select n prime numbers in the sequence and assign them as {p _1,l ,p _2,l ,...,p _n,l }, where l∈{1,2,...,m-1}.

Optionally, the sub-key generating device further includes:

The sub-key distribution unit is used to encrypt the sub-key information {s _i,1 ,s _i,2 ,...,s _i,m } by using public key encryption or private key encryption and distribute it to the i-th participants.

On the other hand, the present invention also provides a device for restoring a key, comprising:

i_r∈A，|A|≥t_l，

其中，l∈{1,…,m}，t+m-1＝t'，2≤t≤t'≤n，n为参与者总数，t为最小门限，t'为最大门限，m为可调整的门限总数；a sub-key obtaining unit, configured to: in the case of starting the lth threshold t _l (t _l =t+l-1), obtain the sub-keys of at least t _l participants

i _r ∈A, |A|≥t _l ,

Among them, l∈{1,...,m}, t+m-1=t', 2≤t≤t'≤n, n is the total number of participants, t is the minimum threshold, t' is the maximum threshold, m is the available threshold The total number of thresholds adjusted;

的子矩阵

计算密钥相关值S，其中

key correlation value restoration unit for prime number matrix according to

submatrix of

Calculate the key correlation value S, where

The key restoration unit is used to restore the key s according to the key related value S.

Optionally, restore the key s according to the key-related value S according to the following steps:

s≡S mod p ₀ , where p ₀ is said prime number p ₀ .

The method can realize the access structure of any integer threshold between (t,n) and (t',n), and the length of the generated subkey is only longer than the subkey under a single threshold access structure (t'-t )/(t-1) times share (t'-t+1) thresholds. Especially when t' is large, the sub-key length of the invention is reduced by at least almost 50% compared with (t'-t+1) independent threshold schemes, and can even reach (t'-4)/t' . And each threshold scheme has complete security.

Description of drawings

Other objects and results of the present invention will be more apparent and readily understood by reference to the following description taken in conjunction with the accompanying drawings and the contents of the claims, and as the present invention is more fully understood. In the attached image:

Fig. 1 is the construction method flow chart of prime number matrix;

Fig. 2 is the flow chart of sub-key generation method;

Fig. 3 is the method flow of utilizing subkey to restore key;

Fig. 4 is a sub-key generation device structural diagram;

Fig. 5 is the apparatus flow chart of utilizing subkey to restore key;

Among them: 11-key correlation value calculation unit, 12-subkey calculation unit, 13-subkey determination unit, 14-subkey distribution unit, 21-subkey acquisition unit, 22-key correlation value restoration Unit, 23 - Key Restoration Unit.

The same reference numbers indicate similar or corresponding features or functions throughout the drawings.

Detailed ways

The specific embodiments of the present invention will be described in detail below with reference to the accompanying drawings.

Embodiments of the present invention provide a method and device for generating a subkey with variable thresholds by using the Chinese remainder theorem, and a method and device for restoring a key by using the aforementioned subkey.

In order to realize the dynamic change of the threshold, it is necessary to establish a prime number matrix that conforms to the dynamic change of the threshold number, and then use the prime number matrix to process the key, generate subkeys to each participant and distribute them to them.

First, the construction process of the prime number matrix is analyzed below, and then the sub-key generation method provided by the present embodiment, the method for utilizing the sub-key to restore the key, the sub-key generating device and the device for utilizing the sub-key to restore the key are respectively made. analyze.

1. The establishment of prime number matrix

S01: Determine the total number of participants n and the participant set P={1,2,...,n}.

The total number of participants n represents the number of participants who can distribute the subkey.

S02: Determine the required security parameters t and t' according to the preset security policy, the attacker's ability and the convenience of the participant, 2≤t≤t'≤n, where t is the minimum threshold and t' is the maximum threshold.

The value of t can be appropriately increased when the security policy requirements of the system are higher and the attacker's ability is higher; t'≤n; in addition, t+m-1=t', m is the total number of adjustable thresholds.

S03: Select the required key length λ, and select the prime number p ₀ ∈(2 ^λ-1 , 2 ^λ ].

(下文简写为{p_i,j})，并使{p_i,j}满足下述的关系(1)。S04: Build a prime number matrix

(hereinafter abbreviated as {pi _,j }), and make {pi _,j } satisfy the following relation (1).

l∈{1,…,m}。In relation (1),

l∈{1,…,m}.

The embodiment of the present invention also provides a method for quickly constructing a prime number matrix {pi _,j }, so as to conveniently apply the method for generating a subkey and a method for restoring a key by using the subkey provided by the embodiment of the present invention; the prime number The matrix construction method includes steps S011-S012.

S011: Select n prime numbers from the interval (2 ^λ-1+t'-1 ,2 ^λ-1+t' ] and assign them to {p _1,m ,p _2,m ,...,p _n,m } elements in;

中随机选取n个素数赋值给{p_1,l,p_2,l,…,p_n,l}中的元素，其中l∈{1,2,…,m-1}。S012: According to the value of l in descending order, from the interval

Randomly select n prime numbers from , and assign them to the elements in {p _1,l ,p _2,l ,...,p _n,l }, where l∈{1,2,...,m-1}.

Of course, in other embodiments, the method for constructing the prime number matrix may also adopt other methods provided in the art, and is not limited to the foregoing method.

2. Subkey generation method

On the basis of the prime number matrix {pi _{, j} } provided above, the sub-key can be generated according to the key s, and the specific steps are as in S021-S023.

S021: Determine the key-related value S according to the key s.

素数p₀∈(2^λ-1,2^λ]。Specifically, the key s should satisfy

The prime number p ₀ ∈(2 ^λ-1 ,2 ^λ ].

S022: Calculate s _i,j ≡S mod p _i,j , and use s _{i,j to} form a matrix

where i∈{1,2,…,n} and j∈{1,2,…,m}.

中的第i行元素{s_i,1,s_i,2,…,s_i,m}为分配给第i个参与者的子密钥。S023: Extraction

The i-th row elements in {s _i,1 ,s _i,2 ,...,s _i,m } are the subkeys assigned to the i-th participant.

以使S∈(a_m,b_m]。In this embodiment, in S021, the key correlation value S is determined according to the key s according to the following steps: S=s+αp ₀ , wherein the selection range of the random number α is

so that _{S∈(am ,b m ]} .

Of course, in other embodiments, other methods can also be used to obtain the key related value S according to the key s. For example, the key s is directly used as the key related value S. Of course, at this time, the key s should also satisfy ( a _m , b _m ].

The foregoing sub-key generation method further includes S024: Distribute the sub-key {s _i,1 ,s _i,2 ,...,s _i,m } to the ith participant by using public key encryption or private key encryption. The methods of public key encryption and private key encryption are already known in the art, and will not be described in detail here. Of course, in other embodiments, the sub-key may also be stored in a hardware device such as a dongle or a USB shield, and the distribution of the sub-key is realized by distributing the dongle and the USB shield.

3. The method of using the subkey to restore the key

In practical applications, specifically in social networks, cloud computing and other platforms, the service terminal needs to restore the key through the sub-key held by the participant, and determine whether the restored key conforms to the original key. The method of using the subkey to restore the key includes steps S031-S034.

In the method of using subkeys to restore keys, a key s is shared among n participants, and the key security level requires that at least t _l participants under each threshold give their subkey information to recover key.

The present invention allows keys to have m security levels, and allows m access structures with different thresholds, where l∈{1,2,...,m}, t+m-1=t', 2≤t≤t'≤n , n is the total number of participants, t is the minimum threshold, t' is the maximum threshold, and m is the total number of adjustable thresholds.

S031: In the case of starting the _lth threshold tl (tl=t+ _l - ₁ ), obtain the subkeys of at least tl participants

Among them, l∈{1,2,...,m}, t+m-1=t', t≤t'≤n, n is the total number of participants, t is the minimum total number of participants, and t' is the maximum total number of participants , m is the total number of adjustable thresholds, i _r ∈A, |A|≥t _l ,

不向实现密钥还原的终端发送全部的子密钥信息。当然，在通信安全得到保证的情况下，参与者也可以将自己拥有的子密钥子集直接传输给实现密钥还原的终端，由实现密钥还原的终端根据t_l确定使用子密钥的子集。Specifically, in the case of starting the _lth threshold tl (tl=t+ _l - ₁ ), the terminal used for realizing the key restoration can send the threshold value tl to the participant _, and the participant can send the threshold value tl to the participant according to tl's size to extract the subset of subkeys owned by oneself

All sub-key information is not sent to the terminal that implements key recovery. Of course, if the communication security is guaranteed, the participants can also directly transmit the subset of subkeys they own to the terminal that implements key restoration, and the terminal that implements key restoration determines the use of the subkey according to t _l . Subset.

S032: Extract the submatrix in {pi _,j } according to the size of _tl and the number of _tl participants (of course, it can also be the number of the subkey)

计算密钥相关值S；其中

S033: Utilize submatrix

Calculate the key correlation value S; where

where y _i,j can be obtained using the Euclidean algorithm.

Step S033 is actually a process of calculating S by using the Chinese remainder theorem, and the principle of the Chinese remainder theorem will not be explained in detail here. For details, please refer to the relevant literature.

S034: Restore the key s according to the key-related value S.

Corresponding to the aforementioned method of generating a subkey, in the process of using the subkey to restore the key, s≡S mod p ₀ , where p ₀ is the prime number p ₀ when the prime number matrix is established. Corresponding to the foregoing method, in other embodiments, the key s may also be obtained according to the key correlation value S by using other methods, for example, the key correlation value S is directly used as the key s.

After obtaining the secret key s, the terminal that implements the key restoration compares the secret key s with the key stored by itself, and can determine whether the sub-key sent by each participant is legal, and can also determine whether the identity of each participant is legal. .

Of course, in the process of using the sub-key to restore the key, some information in the sub-key can be sent by the participant to the terminal that implements the key restoration by using public key encryption or private key encryption. Of course, as mentioned above, each participant may also use a dongle or USB shield to send at least some elements of the subkey to a terminal that implements key restoration.

4. Subkey generation device

The sub-key generation apparatus provided in this embodiment includes a key correlation value calculation unit 11 , a sub-key calculation unit 12 and a sub-key determination unit 13 .

素数p₀∈(2^λ-1,2^λ]。The key correlation value calculation unit 11 is used to determine the key correlation value S according to the key s, wherein

The prime number p ₀ ∈(2 ^λ-1 ,2 ^λ ].

中元素s_i,j≡S mod p_i,j；其中，p_i,j是素数矩阵{p_i,j}中的元素，i∈{1,2,…,n}，j∈{1,2,…,m}；The subkey calculation unit 12 is used to calculate

The element s _i,j ≡S mod p _i,j ; where, p _i,j is the element in the prime number matrix {p _i,j }, i∈{1,2,…,n}, j∈{1, 2,…,m};

和

前述关系式中，

l∈{1,…,m}，t为最小参与者总数，t'为最大参与者总数，t≤t'≤n，m为可调整的门限总数，t+m-1＝t'。The prime number matrix {pi _,j } satisfies the relation:

and

In the above relationship,

l∈{1,...,m}, t is the minimum total number of participants, t' is the maximum total number of participants, t≤t'≤n, m is the total number of adjustable thresholds, t+m-1=t'.

中的元素{s_i,1,s_i,2,…,s_i,m}为分配给第i个参与者的子密钥。The subkey determination unit 13 is used to

The elements {s _i,1 ,s _i,2 ,...,s _i,m } in are the subkeys assigned to the i-th participant.

以使S∈(a_m,b_m]。Corresponding to the foregoing method, the key correlation value calculation unit determines the key correlation value S according to the key s according to the following steps: S=s+αp ₀ ; the selection range of the random number α is

so that _{S∈(am ,b m ]} .

In the subkey calculation unit, the prime number matrix {pi _,j } is obtained as follows:

Randomly select n prime numbers from the interval (2 ^λ-1+t'-1 ,2 ^λ-1+t' ] and assign them as {p _1,m ,p _2,m ,...,p _n,m } in sequence;

中随机选取n个素数按照顺序赋值为{p_1,l,p_2,l,...,p_n,l}。According to the value range of l {1,...,m-1} from large to small in order from the interval

Randomly select n prime numbers in the sequence and assign them as {p _1,l ,p _2,l ,...,p _n,l }.

In addition, the sub-key generation device provided in this embodiment may further include a sub-key distribution unit 14, and the sub-key distribution unit 14 is configured to use public key encryption or private key encryption to encrypt the sub-key information {s _{i, 1} ,s _i,2 ,...,s _i,m } are encrypted and distributed to the i-th participant.

5. A device for restoring a key using a subkey

The apparatus for restoring a key by using a subkey provided in this embodiment includes a subkey obtaining unit 21 , a key-related value restoring unit 22 and a key restoring unit 23 .

其中，l∈{1,2,…,m}，t+m-1＝t'，t≤t'≤n，n为参与者总数，t为最小门限，t'为最大门限，m为可调整的门限总数，密钥相关值还原单元22用于素数矩阵{p_i,j}的子矩阵

计算密钥相关值S，其中

The sub-key obtaining unit 21 is configured to obtain the sub-key of at least t _l participants under the condition that the l-th threshold t _l =t+l-1 is activated.

Among them, l∈{1,2,...,m}, t+m-1=t', t≤t'≤n, n is the total number of participants, t is the minimum threshold, t' is the maximum threshold, m is the available threshold The total number of thresholds adjusted, the key correlation value restoration unit 22 is used for the submatrix of the prime number matrix {pi _,j }

Calculate the key correlation value S, where

The key restoration unit 23 is used to restore the key s according to the key correlation value S.

The key restoring unit 23 can restore the key s according to the key correlation value according to the following steps: s≡S modp ₀ , where p ₀ is the aforementioned prime number p ₀ .

6. Examples

According to the foregoing idea, this embodiment provides a specific application example. In a specific application example: t'=4, t=2, the total number of participants n=5, the security parameter λ=8, and a fixed prime number p ₀ =257; accordingly, the determined (a ₁ ,b ₁ ]=( 1908839; 648261852953], (a ₂ , b ₂ ]=(133144723; 358361739593], (a ₃ , b ₃ ]=(164831339; 80635076741]. The prime number matrix p _i,j that satisfies the conditional relationship and is

The key s=110, the key correlation value S=8063507722 is determined, and the sub-keys of the five participants are obtained according to the prime number matrix p _i,j respectively {100 6 10}, {8 10 414}, {82 11 102 }, {128 5 212} and {73 6 304}.

Similarly, using the Chinese remainder theorem, in the case of determining the corresponding threshold, the key correlation value S and the key s can also be obtained by using the aforementioned sub-key restoration.

The subkey provided in this embodiment can share m thresholds under the condition that it carries more (t'-t)/(t-1) information than a single threshold scheme, and each threshold has complete security. The threshold scheme using the aforementioned method has lower reconstruction complexity than similar schemes, and only has a computational complexity of O(t _l ) under each threshold.

In addition, this method can realize the access structure of any integer threshold between (t, n) and (t', n), and the generated subkey can carry more (t'-t) than the scheme under the single threshold access structure )/(t-1) times share (t'-t+1) thresholds. Especially when t' is large, the sub-key length of the invention is reduced by at least almost 50% compared with (t'-t+1) independent threshold schemes, and can even reach (t'-4)/t' . And there is complete security under each threshold scheme.

The aforementioned methods can be applied to core supporting technologies for outsourcing secure computing, access control, privacy protection, data encryption and other requirements under platforms such as distributed security systems, social networks, and cloud computing, and can also be used for groups or groups with conflicting interests that must cooperate. Privilege management and trust management in multi-server and as a basic protocol for secure multi-party computing.

The above are only specific embodiments of the present invention, but the protection scope of the present invention is not limited thereto. Any person skilled in the art can easily think of changes or substitutions within the technical scope disclosed by the present invention. should be included within the protection scope of the present invention. Therefore, the protection scope of the present invention should be based on the protection scope of the claims.

Claims (10)

1. A method for generating a seed key, comprising the steps of:

S101determining a key-dependent value S from the key S, S + α p₀(ii) a Wherein

p₀Is prime and p₀∈(2^λ-1,2^λ]The random number α is selected to be within a range of

So that S ∈ (a)_m,b_m]；

S102, calculating

Element s in (1)_i,j≡Smodp_i,jWherein p is_i,jIs a prime number matrix

Element of (e), i ∈ {1,2, …, n }, j ∈ {1,2, …, m };

the prime number matrix

Satisfy the relation:

and

in the above-mentioned relation, the first and second characteristic,

n is the total number of participants, t is the minimum threshold, t ' is the maximum threshold, t is not less than t ' and not more than n, m is the total number of adjustable thresholds, and t + m-1 is t ';

s103: extraction of

Element of row i of (1 s) { S }_i,1,s_i,2,…,s_i,mIs the subkey assigned to the ith participant.

2. The subkey generation method of claim 1, wherein the prime number matrix is a matrix of prime numbers

The element in (1) is obtained by the following method:

slave interval (2)^λ-1+t'-1,2^λ-1+t']N prime numbers are selected to be assigned to { p_1,m,p_2,m,…,p_n,mThe elements in (1);

sequentially ranging from large to small according to the value of l

In the method, n prime numbers are randomly selected to be assigned to { p_1,l,p_2,l,…,p_n,lWhere l ∈ {1,2, …, m-1 }.

3. The subkey generation method according to claim 1, further comprising:

s104: the sub-key s is encrypted by adopting a public key encryption method or a private key encryption method_i,1,s_i,2,...,s_i,mEncrypted and distributed to the ith participant.

4. A method for recovering a secret key, comprising:

s501: at the start of the first threshold t_l(t_lT + l-1), at least t is obtained_lIn the subkeys of a participant

|A|≥t_l，

Wherein l ∈ {1,2, …, m }, t + m-1 ═ t ', t is more than or equal to 2 and less than or equal to t ', and is less than or equal to n, n is the total number of participants, t is the minimum threshold, t ' is the maximum threshold, and m is the total number of adjustable thresholds;

s502: using a matrix of prime numbers

Is sub-matrix of

Calculating a key correlation value S, wherein

Wherein,

the prime number matrix

Satisfy the relation:

and

in the above-mentioned relation, the first and second characteristic,

n is the total number of participants, t is the minimum threshold, t ' is the maximum threshold, t is not less than t ' and not more than n, m is the total number of adjustable thresholds, and t + m-1 is t ';

s503: and restoring the secret key S according to the secret key correlation value S.

5. Method for recovering a secret key according to claim 4, characterized in that the secret key S is recovered from the secret key correlation value S according to the following steps:

s≡Smodp₀wherein p is₀Is prime, and p₀∈(2^λ-1,2^λ]。

6. A subkey generation apparatus, comprising:

a key-related value calculating unit for determining a key-related value S, S + α p from the key S₀(ii) a Wherein

p₀Is prime and p₀∈(2^λ-1,2^λ]The random number α is selected to be within a range of

So that S ∈ (a)_m,b_m]；

A sub-key calculation unit for calculating

Middle element s_i,j≡Smodp_i,jWherein p is_i,jIs a prime number matrix

Element of (e), i ∈ {1,2, …, n }, j ∈ {1,2, …, m };

the prime number matrix

Satisfy the relation:

and

in the above-mentioned relation, the first and second characteristic,

t is the minimum threshold, t ' is the maximum threshold, t is more than or equal to 2 and less than or equal to t ', n is less than or equal to n, m is the total number of the adjustable thresholds, and t + m-1 is t ';

a sub-key determination unit for determining a sub-key

Element { s } of (1)_i,1,s_i,2,...,s_i,mIs the subkey assigned to the ith participant.

7. The subkey generation apparatus of claim 6, wherein the prime number matrix is a matrix of prime numbers

The element in (1) is obtained by the following method:

slave interval (2)^λ-1+t'-1,2^λ-1+t']In the method, n prime numbers are randomly selected and assigned as { p ] according to the sequence_1,m,p_2,m,...,p_n,m}；

Sequentially ranging from large to small according to the value range {1, …, m-1} of l

In the method, n prime numbers are randomly selected and assigned as { p ] according to the sequence_1,l,p_2,l,...,p_n,l}。

8. The subkey generation apparatus according to claim 6, further comprising:

a sub-key distribution unit for distributing sub-key information { s ] by public key encryption or private key encryption_i,1,s_i,2,...,s_i,mEncrypted and distributed to the ith participant.

9. An apparatus for recovering a secret key, comprising:

subkeyAn acquisition unit configured to: at the start of the first threshold t_l(t_lT + l-1), at least t is obtained_lIn the subkeys of a participant

|A|≥t_l，

Wherein l ∈ {1, …, m }, t + m-1 ═ t ', t is more than or equal to 2 and less than or equal to t ', t is less than or equal to n, n is the total number of participants, t is the minimum threshold, t ' is the maximum threshold, and m is the total number of adjustable thresholds;

a key correlation value recovery unit for using the prime number matrix

Is sub-matrix of

Calculating a key correlation value S, wherein

Wherein the prime number matrix

Satisfy the relation:

and

in the above-mentioned relation, the first and second characteristic,

n is the total number of participants, t is the minimum threshold, t ' is the maximum threshold, t is not less than t ' and not more than n, m is the total number of adjustable thresholds, and t + m-1 is t ';

and the key recovery unit is used for recovering the key S according to the key correlation value S.

10. The apparatus for recovering a secret key according to claim 9, wherein the secret key S is recovered based on the secret key correlation value S according to the following steps:

s≡Smodp₀wherein p is₀Is prime, and p₀∈(2^λ-1,2^λ]。

Images